Vending Machine

Question

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.

Solution

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.

Sample

# 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)