Overview
Design a vending machine that sells products from slots. Requirements: an operator loads products with prices and quantities; a customer inserts coins or notes, selects a product, receives the product and change; the customer can cancel for a full refund; the machine rejects selections without enough money or stock, and cannot sell if it cannot make exact change.
This is the canonical State pattern problem: Idle, HasMoney, Dispensing, and OutOfService states handle the same events differently. Change-making uses a greedy algorithm over available coin denominations with inventory checks (Chain of Responsibility works too). Inventory, the coin box, and the display are separate collaborators.
Before you pay, they ignore 'give me that'. After you pay, they hand it over and count change. If the shelf is empty, they refund you. The script depends on where you are in the transaction.
When to use it
- Very common LLD interview question.
- Demonstrating the State pattern.
- Practicing money handling and change-making.
Where it shows up in interviews
Recognize it when: same button behaves differently by mode.
- Design a vending machine
- Design an ATM
- Design a coffee machine
Where it is used in real software
Real machines implement MDB (Multi-Drop Bus) state machines for coin mechanisms and bill validators.
Transactions progress through scan, pay, and dispense receipt states.
Similar money-in, select, change-out flows.
Key terms
- Slot / product
- Location with product, price, quantity.
- Coin inventory
- Count per denomination for change.
- State
- Idle, HasMoney, Dispensing, OutOfService.
- Greedy change
- Largest denominations first, within available counts.
How it works, step by step
- 1Clarify
Coins vs notes, card payment, change rules, operator actions.
- 2Entities
VendingMachine (context), State implementations, Inventory, CoinBox, Product.
- 3State transitions
Idle -> HasMoney -> Dispensing -> Idle / OutOfService.
- 4Change-making
Compute change before dispensing; if impossible, refuse and refund.
- 5Edge cases
Cancel mid-way, invalid slot, sold out, exact change only.
STEP 1insert(100) in Idle: credit 100, move to HasMoney.
Events by state
Machine behavior
| Event | Idle | HasMoney | OutOfService |
|---|---|---|---|
| insert(coin) | Credit, go HasMoney | Add credit | Return coin |
| select(slot) | 'Insert money' | Validate, dispense, change | 'Out of service' |
| cancel() | Nothing | Refund, go Idle | Nothing |
| service(on/off) | Toggle | Refund then toggle | Toggle |
NOWEvent: insert(coin) | Idle: Credit, go HasMoney | HasMoney: Add credit | OutOfService: Return coin
Each column is a State class; the machine delegates every event to the current state.
Implementation
import java.util.*; enum Coin { NICKEL(5), DIME(10), QUARTER(25), DOLLAR(100); final int cents; Coin(int c) { cents = c; } } record Product(String name, int priceCents) {} final class Inventory { private final Map<String, Product> products = new HashMap<>(); private final Map<String, Integer> stock = new HashMap<>(); void load(String slot, Product p, int qty) { products.put(slot, p); stock.merge(slot, qty, Integer::sum); } Product product(String slot) { return Optional.ofNullable(products.get(slot)).orElseThrow(() -> new IllegalArgumentException("Unknown slot")); } boolean inStock(String slot) { return stock.getOrDefault(slot, 0) > 0; } void take(String slot) { stock.merge(slot, -1, Integer::sum); }} final class CoinBox { private final EnumMap<Coin, Integer> coins = new EnumMap<>(Coin.class); void add(Coin c, int n) { coins.merge(c, n, Integer::sum); } /** Greedy change within available counts; empty if impossible. Does not mutate on failure. */ Optional<List<Coin>> change(int amount) { List<Coin> out = new ArrayList<>(); EnumMap<Coin, Integer> temp = new EnumMap<>(coins); List<Coin> desc = new ArrayList<>(List.of(Coin.values())); Collections.reverse(desc); for (Coin c : desc) { while (amount >= c.cents && temp.getOrDefault(c, 0) > 0) { amount -= c.cents; temp.merge(c, -1, Integer::sum); out.add(c); } } if (amount != 0) return Optional.empty(); coins.clear(); coins.putAll(temp); return Optional.of(out); }} interface State { void insert(VendingMachine m, Coin c); void select(VendingMachine m, String slot); void cancel(VendingMachine m);} final class VendingMachine { final Inventory inventory = new Inventory(); final CoinBox coinBox = new CoinBox(); final List<Coin> inserted = new ArrayList<>(); State state = new Idle(); final List<String> display = new ArrayList<>(); void insert(Coin c) { state.insert(this, c); } void select(String slot) { state.select(this, slot); } void cancel() { state.cancel(this); } int credit() { return inserted.stream().mapToInt(c -> c.cents).sum(); } List<Coin> refund() { List<Coin> r = List.copyOf(inserted); inserted.clear(); return r; } void show(String msg) { display.add(msg); }} final class Idle implements State { public void insert(VendingMachine m, Coin c) { m.inserted.add(c); m.state = new HasMoney(); m.show("Credit " + m.credit()); } public void select(VendingMachine m, String slot) { m.show("Insert money first"); } public void cancel(VendingMachine m) {}} final class HasMoney implements State { public void insert(VendingMachine m, Coin c) { m.inserted.add(c); m.show("Credit " + m.credit()); } public void select(VendingMachine m, String slot) { Product p = m.inventory.product(slot); if (!m.inventory.inStock(slot)) { m.show(p.name() + " sold out"); return; } if (m.credit() < p.priceCents()) { m.show("Price " + p.priceCents() + ", credit " + m.credit()); return; } m.inserted.forEach(c -> m.coinBox.add(c, 1)); // coins go into the box first Optional<List<Coin>> change = m.coinBox.change(m.credit() - p.priceCents()); if (change.isEmpty()) { m.inserted.forEach(c -> m.coinBox.add(c, -1)); // take the customer's coins back out m.show("Exact change only, refunding " + m.refund()); m.state = new Idle(); return; } m.inventory.take(slot); m.inserted.clear(); m.show("Dispensed " + p.name() + ", change " + change.get()); m.state = new Idle(); } public void cancel(VendingMachine m) { m.show("Refunded " + m.refund()); m.state = new Idle(); }}Complexity and performance
State dispatch.
Canonical coin systems.
Trade-offs
Greedy is optimal for canonical coin systems (US coins) but can fail with limited counts or unusual denominations; DP finds a solution whenever one exists.
State classes scale to rich behavior; a table is shorter for a simple machine.
Variants and related techniques
A PaymentMethod strategy: coins, card, or mobile wallet.
Observer publishes low-stock events to the operator.
Common mistakes
- Dispensing before verifying change.
Fix: Check stock and change first; then commit all updates.
- Status checks in every method (switch on state).
Fix: Use the State pattern.
- Using floating point for money.
Fix: Use integer cents.
Interview questions
Why use the State pattern for a vending machine?
Every action (insert, select, cancel) behaves differently depending on whether money is inserted, an item is dispensing, or the machine is out of service. State classes encapsulate each mode's behavior and transitions instead of repeating switches.
What if the machine cannot give change?
Compute change before dispensing. If it is impossible, either refuse the selection and keep the credit so the user can pick another item, or refund; never dispense without change.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Vending machine with State pattern | Medium | Transitions. |
| Add card payments and low-stock alerts | Hard | Strategy + Observer. |