Vending Machine

State Machine Design

Design a machine that takes coins, sells a product, returns change and lets the customer cancel. The interviewer is looking for the State pattern done properly, and for what happens when the machine cannot make change.

Overview

A customer puts coins in, picks a product by its code, and gets the product and any change back. They can cancel and get their coins back at any point before the product drops. The machine keeps stock and a box of coins, refuses what it cannot do, and is never left half-way through a sale.

This is the standard exercise for the State pattern. The machine behaves differently depending on where it is in a sale: a coin is welcome while paying and refused while a product is dropping; a cancel refunds coins in one state and means nothing in another. Interviewers watch whether you put each of those rules where it belongs, in a state class, instead of in a growing if-chain, and whether you notice the one rule most candidates miss: a sale must be checked for change before the product is released.

Scoping the problem

Which coins, and are bills or cards in scope? — Payment is a strategy; coins first keeps the state machine in focus — Coins only; cards as a follow-up
Can a product be selected before paying? — Decides whether there is a Selected state before Paying — Pay first, then select
What if the machine cannot make exact change? — Refuse the sale, or keep the difference — Refuse, keep the customer's coins, let them cancel
Can the customer cancel? When? — Cancel is valid while paying, not while dispensing — Yes, until the product is released
One customer at a time? — The machine is a single shared resource — Yes; one lock around each action
Who restocks and empties the cash box? — An operator API outside the sale flow — A restock method; a maintenance state as a follow-up

States and actions

Write down the state machine before any class. Three states cover a sale. Dispensing exists because releasing a product takes time on a real machine and nothing else may happen meanwhile.

The state-by-action table is the same information as the diagram. Draw one of them; keep the other in your head to check the code.

insert_coin — Accept, go to Paying — Accept — Refused
select — Refused — Check stock, funds and change; on success go to Dispensing — Refused
dispense — Refused — Refused — Release product and change, go to Idle
cancel — Refused — Refund all coins, go to Idle — Refused

Seven of the twelve cells are the same word, refused. That is why the abstract State class refuses everything by default and each concrete state overrides only the cells it allows.

Making change

Change is planned greedily, largest coin first, using only coins the machine actually holds. The customer's own coins count, because they are in the machine by the time change is needed. If the plan comes up short, the sale is refused and the machine stays in Paying with the customer's money intact.

10 — 3 quarters, 1 dime, 1 nickel — dime — Sale goes ahead
35 — 3 quarters, 1 nickel — quarter, then 10 short with only a nickel left — Refused; customer can cancel
35 — 3 quarters, 1 nickel, 1 dime — quarter, dime — Sale goes ahead
0 — anything — nothing — Exact payment, no change

With an unlimited supply of each US coin (5, 10, 25 and 100 cents), largest-first gives the fewest coins. A real machine holds a limited supply, and then greedy can refuse a sale that was possible: owing 30 cents with one quarter and three dimes, it takes the quarter and is 5 short. Greedy is also not optimal for an arbitrary coin set, so if the interviewer changes the denominations or asks for this case, say that a dynamic-programming version is needed.

Atomicity and one customer at a time

Every public method takes the machine's lock, so an action runs to completion before the next one starts, even if a kiosk API sends two requests at once. Inside an action the state does the risky work in a safe order: it checks stock, funds and change before it changes anything, and it only takes the product out of stock in dispense, after all checks have passed. A failure in select therefore leaves nothing to undo.

Look up the product — OutOfStock — Paying, coins kept
Compare balance with price — InsufficientFunds — Paying, coins kept
Plan the change — CannotMakeChange — Paying, coins kept, the customer's coins pulled back out of the cash box
Release the product, pay out change — Nothing left that can fail in software — Idle

What you will be able to do

Draw the state machine and the state-by-action table before writing a class.
Explain why the abstract state refuses everything and each state overrides a few cells.
Order the checks in select so that a refused sale leaves nothing to undo.
Make change from coins the machine holds and handle the case where it cannot.
Make each action atomic with one lock, and say what a kiosk API adds.

Functional requirements

Accept coins of fixed denominations (5, 10, 25 and 100 cents) one at a time
Select a product by code once enough money is in; the machine checks stock, funds and change before it commits
Dispense the product and the exact change, made from coins the machine holds
Cancel at any point while paying and get every inserted coin back
Refuse actions that make no sense in the current state, with a clear error and no side effect
Restock products and load coins through operator methods

Non-functional requirements

Every action is atomic: one lock on the machine, so a kiosk API cannot interleave two customers
A refused sale leaves the machine exactly as it was: stock, cash box and the customer's coins unchanged
The three state objects hold no per-sale data, so they are created once and reused
Adding a state (for example Maintenance) or a payment method is a new class, not a change to the machine

Interview questions

Why the State pattern instead of a status field and if statements?
How would you add card payments?
Should the state objects be created once or on every transition?
What happens when the machine cannot make change?
How do you keep a sale from being left half done?
How would you add a Maintenance state for restocking?