Cruxly › Low-level design › LLD Exercises

Vending Machine

a state machine that must never dispense without payment, and never eat money

Prompt: design a vending machine. A user selects an item, inserts money (coins or notes, in increments), and the machine dispenses the item and returns change — or returns all inserted money if the user cancels or the item is unavailable.

45 minutes. The interesting part is not the inventory. It's proving the state machine cannot dispense without full payment and cannot eat a cancelled user's money.

Applying the five moves: nouns are Item, State (idle, selecting, collecting-payment, dispensing), and a running insertedAmount — the "state" noun is the one candidates skip, and it's the one the invariant depends on. The invariant is "an item is dispensed if and only if insertedAmount >= price, and every state except mid-dispense is refundable" — state that before drawing the state diagram, because it's what tells you which transitions to disallow. There's no strong interface seam here worth forcing (payment method is out of scope per this prompt) — naming that explicitly is a better answer than inventing a PaymentStrategy interface nothing asked for. The concurrency sentence: a single physical machine serves one transaction at a time, so the honest answer is "no concurrency within one machine" — say that, then name multi-machine inventory sync as the separate, harder problem if it comes up.

Scope, and why this is a state machine problem first

In scope: item selection, incremental payment, change calculation, dispensing, cancellation/refund. Out of scope (say it): card payment integration (a different, external-system problem — name it and move on), restocking/inventory replenishment, multi-currency.

The states, named before any class exists:

IDLE            -- no selection, no money
SELECTED        -- item chosen, waiting for payment
PAYMENT_OK      -- enough money inserted, ready to dispense
DISPENSING      -- mechanically dropping the item (brief, but real)
DISPENSED       -- item dropped; only remaining work is returning change

The one sentence that shapes everything else: money is refundable in every state except DISPENSING and after. Before the item physically drops, cancelling must return every coin inserted. After it drops, the transaction is complete — the machine owes only correct change, never a full refund, because the user already has the product. Getting this boundary right, and saying precisely which state it falls on, is the actual exercise; the rest is bookkeeping.

A vending machine is a small number of states with a large number of illegal transitions — DISPENSING without PAYMENT_OK, a second item selected while one is already SELECTED, money accepted in DISPENSED. Naming the illegal transitions explicitly, before writing any code, is what separates a design that happens to work from one that cannot be made to misbehave.

The classes — full implementation

The state itself is an enum with behaviour, not a string checked by if-statements everywhere. A string-typed status field invites exactly the illegal transitions named above, because nothing stops code from setting it to anything from anywhere.

public enum MachineState {
    IDLE {
        @Override MachineState onSelect(VendingMachine m, String code) {
            if (!m.inventory().has(code)) return this;         // unknown code: stay IDLE
            m.setSelected(code);
            return SELECTED;
        }
    },
    SELECTED {
        @Override MachineState onInsertMoney(VendingMachine m, Coin c) {
            m.addFunds(c);
            Item item = m.inventory().peek(m.selectedCode());
            return m.funds() >= item.price() ? PAYMENT_OK : this;
        }
        @Override MachineState onCancel(VendingMachine m) {
            m.refundAll();
            return IDLE;
        }
    },
    PAYMENT_OK {
        @Override MachineState onDispense(VendingMachine m) {
            return DISPENSING;
        }
        @Override MachineState onCancel(VendingMachine m) {
            m.refundAll();                                     // still refundable — nothing dispensed yet
            return IDLE;
        }
    },
    DISPENSING {
        @Override MachineState onMechanicalComplete(VendingMachine m) {
            m.inventory().take(m.selectedCode());
            return DISPENSED;
        }
        // no onCancel override: cancellation is illegal here by omission, not by a runtime check
    },
    DISPENSED {
        @Override MachineState onSettle(VendingMachine m) {
            m.returnChange();                                  // change only, never a full refund
            m.reset();
            return IDLE;
        }
    };

    // Default: every transition not explicitly overridden is a no-op that stays put.
    MachineState onSelect(VendingMachine m, String code) { return this; }
    MachineState onInsertMoney(VendingMachine m, Coin c) { return this; }
    MachineState onCancel(VendingMachine m) { return this; }
    MachineState onDispense(VendingMachine m) { return this; }
    MachineState onMechanicalComplete(VendingMachine m) { return this; }
    MachineState onSettle(VendingMachine m) { return this; }
}

This is the same "make illegal states unrepresentable" discipline used for the chess board's move legality elsewhere in this track, applied to a physical machine instead of a rule engine. DISPENSING.onCancel simply doesn't exist — there is no code path that can refund after the drop has started, not a guard clause hoping to catch it.

public class VendingMachine {
    private MachineState state = MachineState.IDLE;
    private final Inventory inventory;
    private final List<Coin> insertedCoins = new ArrayList<>();
    private String selectedCode;

    public synchronized void select(String code)      { state = state.onSelect(this, code); }
    public synchronized void insertMoney(Coin c)       { state = state.onInsertMoney(this, c); }
    public synchronized void cancel()                  { state = state.onCancel(this); }
    public synchronized void dispense()                { state = state.onDispense(this); }
    public synchronized void mechanicalComplete()      { state = state.onMechanicalComplete(this); }
    public synchronized void settle()                  { state = state.onSettle(this); }

    void addFunds(Coin c)   { insertedCoins.add(c); }
    long funds()            { return insertedCoins.stream().mapToLong(Coin::valueCents).sum(); }
    void refundAll()        { dispenseCoins(insertedCoins); insertedCoins.clear(); selectedCode = null; }
    void returnChange()     { dispenseCoins(makeChange(funds() - inventory.peek(selectedCode).price())); }
    void reset()            { insertedCoins.clear(); selectedCode = null; }
    // dispenseCoins(), makeChange(), inventory(), peek(), take() omitted — mechanical, not the exercise
}

Every public method is synchronized on the machine itself — a vending machine has exactly one hopper, one coin slot, one keypad; there is no scenario where two operations legitimately happen at once, so a single coarse lock is the correct answer here, not an over-engineered concern. This is worth contrasting explicitly with the rate limiter's per-key lock elsewhere in this track: the right lock granularity depends on whether concurrent operations are ever legitimate, and here they never are.

Change-making, and the two failure modes that actually matter

Change calculation is a coin problem, and the greedy algorithm is usually — but not always — optimal. Greedy (always take the largest denomination that fits) is optimal for canonical coin systems (like most real currencies), but the interviewer may push on this: "what if a denomination set makes greedy suboptimal?" The honest answer is dynamic programming over the minimum-coins problem, and naming that this is the well-known coin-change DP, not a novel algorithm, is the right level of depth here — the exercise is not testing algorithm design, it's testing whether you notice greedy is an assumption.

The two failure modes that actually matter, both about honesty toward the user's money:

The machine cannot make correct change with its current coin stock. This must be checked before accepting the transaction as final, not discovered after the item has dropped — PAYMENT_OK should verify that exact change is physically possible given current coin inventory, and if not, refuse the sale and refund everything rather than dispensing the item and shortchanging the user or, worse, dispensing with no change mechanism to fall back on.

A coin jam or mechanical failure during DISPENSING. The state machine above has no transition out of DISPENSING except onMechanicalComplete — a real machine needs a timeout or a sensor-driven failure path back out, because a mechanical fault otherwise leaves the machine stuck in a state with no defined exit, holding the user's money with the item never dispensed. Naming this unprompted, as the gap the clean state diagram doesn't show, is what separates a design that looks correct from one that has actually been thought through against hardware.

Follow-ups they will ask

"Add a restocking/admin mode." A second, disjoint state graph reachable only via a physical key or admin code, not a state layered onto the customer-facing one — restocking and vending should never be representable as simultaneously possible, so keep them as two machines that share the inventory object rather than one machine with an ADMIN branch tangled through every customer state.

"Support multiple items dispensing from different slots with independent stock." The Inventory is already a seam (has, peek, take keyed by code) — this scales by making it a map from code to (item, count, slot), no change to the state machine itself. Say this explicitly: the state machine models the transaction lifecycle, not the inventory shape, and that separation is why this follow-up costs nothing.

"What if two users could interact with the machine at once (a networked machine, or a queue)?" Reject the premise directly: a physical vending machine's coin slot and keypad are exclusive hardware resources — there is no legitimate concurrent transaction, so this is exactly the case (contrasted with the rate limiter) where a single coarse lock is correct, and adding finer-grained concurrency control would be solving a problem the hardware doesn't have.

How to say it in the interview

"A vending machine is a small number of states with a large number of illegal transitions between them, so I want to enumerate the states first, make illegal transitions unrepresentable, and treat money as a running total that is refundable at every state except the one where the item has already dropped."

Checklist

Enumerated the states before writing any class, including which transitions are illegal
Identified the exact state boundary where refund becomes change-only
Used an enum with per-state behaviour rather than a status field checked by if-statements
Left illegal transitions absent from the state definition rather than guarded by a runtime check
Used one coarse lock on the whole machine rather than fine-grained per-operation locking
Named that greedy change-making is optimal only for canonical denomination sets
Verified exact change is possible before finalizing payment, not after dispensing
Named the missing failure exit from DISPENSING as a real gap, not an oversight to leave implicit
Modelled admin/restocking as a separate state graph sharing inventory, not a branch on the customer state machine

Practice this interactively