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.