Vending Machine — Low Level Design

Context#

A vending machine sells packaged goods (snacks, drinks) from a fixed inventory of slots. A customer selects a product, inserts coins, and either gets the product with change or aborts and gets the inserted coins back. The problem is the smallest realistic state-machine LLD prompt — five or six states, a handful of inputs, and a coin-change algorithm — which is exactly why interviewers reach for it: it forces a clean State pattern in 20 lines instead of letting the candidate hide behind volume.

The interviewer’s hidden objectives, in roughly the order they will be tested:

Can you identify the states — Idle, Selecting, AcceptingMoney, Dispensing, OutOfStock — and the events that drive transitions?
Can you use the State pattern instead of an enum-and-switch?
Can you defend the coin-change algorithm? Greedy works for standard denominations; dynamic programming is needed when it doesn’t.
Can you identify the entities — machine, slot, product, coin, balance — and the relationships?
Can you narrate a flow for a customer who underpays, then adds more, then aborts?

Requirements (functional and non-functional)#

Scoping is the heaviest-weighted moment of the round. The defaults below are what most interviewers accept; flag anything outside them.

Functional — in scope.

The machine has N fixed slots, each tied to a product and holding up to K units (default 10).
A customer selects a slot by code; the machine quotes a price.
The customer inserts coins in supported denominations (₹1, ₹2, ₹5, ₹10).
When the inserted balance covers the price, the machine dispenses the product and the change.
The customer can cancel at any point in selection or money-acceptance and recover the inserted coins.
If a slot’s quantity reaches zero, the machine rejects further selections of that slot until restocked.

Functional — out of scope (called out explicitly). Card or UPI payments, refrigerated slots with temperature monitoring, customer accounts and loyalty, networked telemetry, slot-level marketing displays. Mentioned so the interviewer knows you saw them; not discussed unless asked.

Non-functional.

The machine has on the order of 50 slots and serves one customer at a time — there is one physical front panel.
Selection and dispense decisions in well under 100 ms — humans hate vending machines that “think”.
The machine should not give wrong change. Ever. (This is the requirement candidates most often understate.)
The machine should not dispense if it cannot give exact change.

Use case diagram#

                ┌────────────────┐
                │    Customer    │
                └────────┬───────┘
                         │
         ┌───────────────┼───────────────┐
         ▼               ▼               ▼
    [select product] [insert coins] [cancel transaction]
         │               │               │
         ▼               ▼               ▼
   ┌──────────────────────────────────────┐
   │       Vending Machine System         │
   └────────────────┬─────────────────────┘
                    ▲
                    │
            ┌───────────────────┐
            │     Operator      │   …  restock, collect cash, run diagnostics
            └───────────────────┘

Two actors (Customer, Operator) and three customer-side use cases. The operator actor matters because restock is the event that lifts an OutOfStock slot back to selectable.

Class diagram#

                          ┌──────────────────────────┐
                          │     VendingMachine       │
                          ├──────────────────────────┤
                          │ slots : Map<String,Slot> │
                          │ coinBank : CoinBank      │
                          │ changer : ChangeStrategy │
                          │ state : MachineState     │
                          │ session : Session        │
                          ├──────────────────────────┤
                          │ select(slotCode)         │
                          │ insertCoin(coin)         │
                          │ cancel()                 │
                          │ restock(slotCode, units) │
                          └──────────┬───────────────┘
                                     │
              ┌──────────────────────┼────────────────────┐
              ▼                      ▼                    ▼
       ┌────────────┐         ┌────────────────┐   ┌────────────────────┐
       │ IdleState  │         │ SelectingState │   │AcceptingMoneyState │
       └────────────┘         └────────────────┘   └────────────────────┘
                                      │
                ┌─────────────────────┼─────────────────────┐
                ▼                                           ▼
        ┌────────────────┐                         ┌────────────────┐
        │ DispensingState│                         │ OutOfStockState│
        └────────────────┘                         └────────────────┘

         ┌──────────────────┐    ┌────────────────────────┐    ┌──────────────────┐
         │      Slot        │    │      Session           │    │   CoinBank       │
         ├──────────────────┤    ├────────────────────────┤    ├──────────────────┤
         │ code, product    │    │ selectedSlot           │    │ counts: Map<Coin,Int> │
         │ price, quantity  │    │ balance : Money        │    │ accept(coin)     │
         ├──────────────────┤    │ insertedCoins: List<Coin> │ │ withdraw(coins)  │
         │ dispense()       │    └────────────────────────┘    └──────────────────┘
         └──────────────────┘
                                                ┌──────────────────────┐
                                                │   ChangeStrategy     │◁── Greedy, DP
                                                ├──────────────────────┤
                                                │ change(amount, bank) │
                                                └──────────────────────┘

Two patterns are doing the load-bearing work:

State pattern on VendingMachine — every method (select, insertCoin, cancel) delegates to the current state. The state owns the transition rule and rejects events that do not apply. This is what kills the spaghetti if (state == IDLE && event == SELECT) ….
Strategy pattern on ChangeStrategy — GreedyChangeStrategy (works for canonical denominations) and DpChangeStrategy (works for arbitrary sets). The machine does not switch on denomination.

What is not in the diagram and that is deliberate:

Slot does not carry its own state machine. Quantity zero is captured by the machine’s OutOfStock state when that slot is selected; otherwise quantity is just a count.
Session is a lightweight value, not an aggregate. It is the in-flight transaction; when the machine returns to Idle, the session is cleared. No persistence.
CoinBank is separate from Session.insertedCoins. The bank is the machine’s reservoir of change; the session holds what this customer has put in. Merging them would mean the machine cannot give correct change if the customer cancels.

Sequence diagram (key flows)#

The happy path — select, pay, dispense:

 Customer      VendingMachine    State              Slot       CoinBank      ChangeStrategy
   │ select(A1)    │                │                │             │              │
   │──────────────►│                │                │             │              │
   │               │ select(A1)     │                │             │              │
   │               │───────────────►│ (IdleState)    │             │              │
   │               │                │ slots.get(A1)  │             │              │
   │               │                │───────────────►│             │              │
   │               │                │ quantity > 0?  │             │              │
   │               │                │◄───── yes ─────│             │              │
   │               │ → SelectingState              │             │              │
   │ insertCoin(₹10)│                │                │             │              │
   │──────────────►│                │                │             │              │
   │               │ insertCoin     │                │             │              │
   │               │───────────────►│ (SelectingState)              │             │
   │               │                │ session.add(₹10) → AcceptingMoneyState     │
   │ insertCoin(₹10)│                │                │             │              │
   │──────────────►│                │                │             │              │
   │               │ insertCoin     │                │             │              │
   │               │───────────────►│ (AcceptingMoneyState)         │             │
   │               │                │ balance ≥ price?              │             │
   │               │                │            yes                │             │
   │               │                │ change(balance-price, bank) ────────────────►│
   │               │                │           coins                              │
   │               │                │◄─────────────────────────────────────────────│
   │               │                │ slot.dispense() ─────────────►│             │
   │               │                │ bank.accept(inserted)                        │
   │               │                │ bank.withdraw(coins)                         │
   │               │                │ → DispensingState → IdleState                │
   │   product, change │            │                │             │              │
   │◄──────────────│                │                │             │              │

The cancel flow (from AcceptingMoneyState):

 Customer      VendingMachine    State              CoinBank
   │ cancel()      │                │                │
   │──────────────►│                │                │
   │               │ cancel()       │                │
   │               │───────────────►│ (AcceptingMoneyState)
   │               │                │ return session.insertedCoins
   │               │                │ → IdleState
   │   coins back  │                │
   │◄──────────────│                │

cancel() returns exactly the coins inserted — the bank is untouched. That is the property that prevents “lost the ₹2, got back two ₹1s” complaints.

Activity diagram (for non-trivial state)#

The machine’s state machine — the centrepiece of the design:

                  ┌─────────┐
                  │  start  │
                  └────┬────┘
                       ▼
              ┌────────────────┐
   ┌─────────►│      Idle      │── select(slot) ─────┐
   │          └────────────────┘                     │
   │                                                 ▼
   │                              [quantity > 0?]
   │                                  │      │
   │                              yes │      │ no
   │                                  ▼      ▼
   │                       ┌──────────────┐  ┌──────────────┐
   │                       │  Selecting   │  │ OutOfStock   │── any input ──┐
   │                       └──────┬───────┘  └──────────────┘               │
   │                              │ insertCoin                              │
   │                              ▼                                         │
   │                       ┌──────────────────┐                             │
   │                       │ AcceptingMoney   │── balance ≥ price ──┐      │
   │                       └──────┬───────────┘                     │      │
   │                              │ cancel                          ▼      │
   │                              ▼                          ┌───────────┐ │
   │                       (refund inserted)                 │ Dispensing│ │
   │                              │                          └─────┬─────┘ │
   │                              ▼                                │       │
   └──────────────────────────────┴────────────────────────────────┴───────┘

OutOfStock is a transient courtesy state — show a message, then bounce back to Idle on any input. Dispensing is also transient — the machine emits the product and change, then returns to Idle. The two “interesting” states with branching behaviour are Selecting and AcceptingMoney.

Java implementation#

A representative slice — the state machine and the greedy change strategy — not the full system.

public enum Coin {
    ONE(1), TWO(2), FIVE(5), TEN(10);
    private final int value;
    Coin(int v) { this.value = v; }
    public int value() { return value; }
}

public interface MachineState {
    void select(VendingMachine m, String slotCode);
    void insertCoin(VendingMachine m, Coin c);
    void cancel(VendingMachine m);
}

public final class IdleState implements MachineState {
    public void select(VendingMachine m, String slotCode) {
        Slot slot = m.slots().get(slotCode);
        if (slot == null) throw new UnknownSlotException(slotCode);
        if (slot.quantity() == 0) { m.setState(new OutOfStockState()); return; }
        m.beginSession(slot);
        m.setState(new SelectingState());
    }
    public void insertCoin(VendingMachine m, Coin c) {
        throw new IllegalStateException("Select a product first");
    }
    public void cancel(VendingMachine m) { /* no-op */ }
}

public final class SelectingState implements MachineState {
    public void select(VendingMachine m, String slotCode) {
        // allow re-selection before any coins inserted
        m.endSession();
        new IdleState().select(m, slotCode);
    }
    public void insertCoin(VendingMachine m, Coin c) {
        m.session().add(c);
        m.setState(new AcceptingMoneyState());
    }
    public void cancel(VendingMachine m) { m.endSession(); m.setState(new IdleState()); }
}

public final class AcceptingMoneyState implements MachineState {
    public void select(VendingMachine m, String slotCode) {
        throw new IllegalStateException("Cancel to change product");
    }
    public void insertCoin(VendingMachine m, Coin c) {
        Session s = m.session();
        s.add(c);
        if (s.balance() >= s.slot().price()) attemptDispense(m);
    }
    public void cancel(VendingMachine m) {
        m.refundSessionCoins();
        m.endSession();
        m.setState(new IdleState());
    }
    private void attemptDispense(VendingMachine m) {
        Session s = m.session();
        int changeAmount = s.balance() - s.slot().price();
        List<Coin> change;
        try {
            change = m.changer().change(changeAmount, m.coinBank());
        } catch (CannotMakeChangeException e) {
            m.refundSessionCoins();
            m.endSession();
            m.setState(new IdleState());
            throw e;
        }
        m.coinBank().acceptAll(s.insertedCoins());
        m.coinBank().withdrawAll(change);
        s.slot().dispense();
        m.deliver(s.slot().product(), change);
        m.endSession();
        m.setState(new IdleState());
    }
}

public final class OutOfStockState implements MachineState {
    public void select(VendingMachine m, String code) { m.setState(new IdleState()); new IdleState().select(m, code); }
    public void insertCoin(VendingMachine m, Coin c) { m.setState(new IdleState()); }
    public void cancel(VendingMachine m) { m.setState(new IdleState()); }
}

public interface ChangeStrategy {
    List<Coin> change(int amount, CoinBank bank) throws CannotMakeChangeException;
}

public final class GreedyChangeStrategy implements ChangeStrategy {
    private static final List<Coin> ORDER = List.of(Coin.TEN, Coin.FIVE, Coin.TWO, Coin.ONE);
    public List<Coin> change(int amount, CoinBank bank) {
        List<Coin> out = new ArrayList<>();
        int remaining = amount;
        Map<Coin, Integer> snapshot = bank.snapshot();
        for (Coin c : ORDER) {
            int available = snapshot.getOrDefault(c, 0);
            while (remaining >= c.value() && available > 0) {
                out.add(c);
                remaining -= c.value();
                available--;
            }
        }
        if (remaining != 0) throw new CannotMakeChangeException(amount);
        return out;
    }
}

public final class VendingMachine {
    private final Map<String, Slot> slots;
    private final CoinBank coinBank;
    private final ChangeStrategy changer;
    private MachineState state = new IdleState();
    private Session session;

    public VendingMachine(Map<String, Slot> slots, CoinBank bank, ChangeStrategy changer) {
        this.slots = slots; this.coinBank = bank; this.changer = changer;
    }

    public synchronized void select(String code) { state.select(this, code); }
    public synchronized void insertCoin(Coin c)   { state.insertCoin(this, c); }
    public synchronized void cancel()             { state.cancel(this); }

    // package-private hooks for the state objects
    Map<String, Slot> slots() { return slots; }
    void setState(MachineState s) { this.state = s; }
    void beginSession(Slot slot) { this.session = new Session(slot); }
    void endSession() { this.session = null; }
    Session session() { return session; }
    CoinBank coinBank() { return coinBank; }
    ChangeStrategy changer() { return changer; }
    void refundSessionCoins() { /* hand back session.insertedCoins to the dispense tray */ }
    void deliver(Product p, List<Coin> change) { /* drop product and change into tray */ }
}

Notes the interviewer will look for:

State objects, not an enum-and-switch. Each state encapsulates “what’s legal here”. Adding a Maintenance state is one new class, no edits.
SelectingState.select allows re-selection. A small ergonomic detail that pays off in the demo — the customer can change their mind before inserting coins.
Greedy change only works for canonical denominations. {₹1, ₹2, ₹5, ₹10} is canonical (greedy is optimal). For non-canonical sets (e.g. {₹1, ₹3, ₹4}), the DP strategy is required — name this even if you don’t write it.
CannotMakeChangeException aborts the transaction and refunds. “Cannot give change” is not “swallow money and dispense”; it is “refund and stay in Idle”.
CoinBank.snapshot() is taken before mutating. The greedy pass plans against a snapshot; the actual withdrawAll happens once the plan is final. This prevents partial withdrawal in the failure path.

Trade-offs and extensions#

Decisions explicitly made and what they cost:

Decision	Why	Cost if requirements change
State pattern on the machine	Five states with distinct rules; an enum-and-switch is a known maintenance trap.	None at this size; pattern earns its keep on day one.
`ChangeStrategy` as a plug-in	Greedy works today; DP is one new class away.	None — this is the right shape now.
`CoinBank` separate from `Session.insertedCoins`	Cancels return the customer’s exact coins; bank stays correct.	None — required for the “never give wrong change” invariant.
`Slot` has no state; `OutOfStock` lives on the machine	Quantity is just a count; the current selection being out is a machine concern.	If many slots need per-slot lifecycle (maintenance, recall), promote `Slot` to its own state machine.
Single `synchronized` on the machine	One physical front panel — no concurrency to speak of.	If a remote API ever talks to the machine, the lock is already in place.
Money as integer paise / smallest unit	Avoids the `double` rounding disaster.	None — always integer-money in vending.
Reject dispense if change cannot be made	Never give wrong change.	Some operators prefer “round down and dispense”; that requires consent at config time, not at decision time.

Likely follow-up extensions and the shape of the answer:

Card / UPI payment. Add a PaymentMethod interface alongside Coin; the AcceptingMoneyState becomes AcceptingPaymentState parameterised by method. Greedy change still applies for any coin refund.
Multi-currency. Coin becomes a Currency plus a denomination; CoinBank is partitioned per currency. The state machine is unchanged.
Loyalty discount. A DiscountStrategy consulted on transition into AcceptingMoneyState; price is computed once and frozen for the session. The state machine is unchanged.
Maintenance mode. New state reachable from Idle; operator transitions in and out. All customer events bounce while Maintenance is active.
Refrigerated slots. Cold chain telemetry is orthogonal; the machine grows a HealthMonitor observer that disables slots when temperature drifts out of band. Existing classes untouched.

Mock interview follow-ups#

Questions interviewers reach for and the briefest correct answer:

“Why the State pattern and not an enum?” — Each state has different legal events; an enum-and-switch grows a quadratic table of if (state == X && event == Y). State objects keep the rules co-located with the data.
“What’s the state machine?” — Idle → Selecting → AcceptingMoney → Dispensing → Idle, with OutOfStock as a transient courtesy state and cancel returning to Idle from Selecting or AcceptingMoney. Show the activity diagram.
“Greedy change isn’t always optimal.” — Correct. For canonical denominations (the Indian and most-Western coin sets) greedy is optimal. For arbitrary sets, use DP. ChangeStrategy lets us swap at config time.
“What if the machine can’t give change?” — Abort the dispense, refund the customer’s exact coins, return to Idle. The bank’s invariant is preserved.
“How do you handle a fake coin?” — Coin validation is the responsibility of the coin acceptor (hardware). The model assumes the Coin object reaching insertCoin has been validated; the machine rejects unknown denominations.
“Two customers at the same time?” — There is one physical front panel; one session at a time. synchronized on the machine ensures no interleaving. If a remote API is added, the lock still holds.
“Where would observers fit?” — On low-stock and low-cash events, so the operator’s monitoring system subscribes without VendingMachine knowing about it. (Observer pattern.)

Parking Lot — sibling Foundational case study; same State + Strategy pair in a different domain.
State Pattern — this writeup is the textbook example.
Strategy Pattern — ChangeStrategy is the textbook example.
Observer Pattern — the answer to the “where would observers fit?” follow-up.
Approaching the OOD Interview — the meta-script that produced this writeup’s structure.