This is an actual question I encountered in an Amazon phone interview in November 2013. You are going to design the money changing algorithm for a vending machine. That is, after any purchase, the machine makes change to users with a combination of coins. And the machine only have 3 types of coins: nickel (5 cents), dime (10 cents) and quarter (25 cents). Coins with higher values are preferred in the change.
Well this is actually a simple question, I could just fill the sum from the highest value coin to the lowest. However I chose to use a simplified version of knapsack algorithm. Whatever, they both works.
# coin values coins = [25, 10, 5] # simple solution for this problem def simple_solution(sum): combination =  for coin in coins: for i in xrange(sum / coin): combination.append(coin) sum %= coin return combination # result: [25, 25, 10, 5] print simple_solution(65)