You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

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

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.