Designing a Vending Machine with the State Pattern

Why the vending machine is a State-pattern problem in disguise

The vending machine is one of the most common machine-coding prompts because it looks trivial (“it takes coins and drops a snack”) but punishes anyone who models it with a pile of boolean flags and if/else. The moment you write if (hasMoney && !dispensing && selectedSlot != null && stock > 0), you have lost. The interviewer is watching whether you recognize that the machine’s behavior depends on a mode it is currently in, and whether each user action (insert coin, select product, dispense, cancel) means something different in each mode.

That is the textbook trigger for the State pattern: an object whose behavior changes when its internal state changes, such that it appears to change its class. Your job in the interview is to (1) name the states, (2) define what each user action does in each state, and (3) make illegal transitions structurally impossible rather than guarded by ad-hoc conditionals.

The single biggest differentiator between an SDE-1 and an SSE answer here is not the code — it is that the SSE says, “Let me enumerate the states and the transition table first, and pin down the money model,” and the SDE-1 starts writing the Coin enum.

Step 1 — Clarify requirements (the few that actually matter)

Spend 60–90 seconds here. Most clarifications are noise; a handful change the design. Ask these, and state your assumptions out loud so you can proceed if the interviewer is passive.

Functional requirements (confirm scope):

• Insert money (coins/notes), select a product, dispense, return change.
• Cancel a transaction and refund money already inserted.
• Admin/maintenance: restock products and refill the change bank.

The clarifications that change the design:

Non-functional: Reliability (never take money without dispensing or refunding), extensibility (new payment types, new products), and a clean separation so the state logic is testable without hardware.

The money model — escrow vs. pooled bank (state this explicitly)

This is the part most candidates leave implicit and then trip over. There are two models:

• Escrow model (what we use): the coins the customer inserts sit in a separate escrow holding area, identified by exact denomination. They are not part of the change bank yet. On cancel(), the machine hands back the exact coins in escrow — refund can never fail. On a successful sale, the escrow coins are committed (merged) into the change bank, and only then are change coins computed and dispensed.
• Pooled-bank model: inserted coins immediately merge into the general bank. This is simpler to code but creates a paradox: on cancel() you must make change for the refund amount out of the pooled bank, which can itself fail to be exact — the very exact-change trap this lesson is about, now applied to refunds.

Step 2 — Core entities and responsibilities

Separate the domain data (what exists) from the state machine (what’s allowed right now). Conflating them is the most common design smell.

• VendingMachine — the context. Holds the current State, the Inventory, the CashRegister, the per-transaction escrow, and the selectedCode. Exposes the user-facing API and delegates every action to the current state object. It owns no branching transition logic itself.
• State (interface) — defines the four actions. Concrete states: IdleState, HasMoneyState, DispensingState, SoldOutState. Each state decides what an action means and which state comes next.
• Inventory — maps a slot/code → (Product, quantity). Answers “is this in stock?”, decrements on dispense, supports restock, reports isEmpty().
• Product — id, name, priceCents (store money in integer cents, never floats).
• CashRegister / ChangeBank — tracks the count of each Coin denomination held in the bank (the change reserve). Computes whether change can be made, dispenses change, and accepts committed escrow coins. This is where the change algorithm lives.
• Coin (enum) — denominations with integer cent values.

Step 3 — The states and the transition table

Define the states precisely:

• Idle — no money inserted, no active transaction, escrow empty. Resting state. insertCoin → escrow the coin, go to HasMoney. select/dispense are invalid.
• HasMoney — coins are sitting in escrow. insertCoin → escrow more. selectProduct → validate stock + funds + change-availability; if OK go to Dispensing, else stay (insufficient funds / out of stock / cannot-make-change-so-refund). cancel → return escrow coins, back to Idle.
• Dispensing — committed to a sale: commit escrow into bank, decrement stock, release product, dispense change, then go to Idle (or SoldOut if the machine is now empty).
• SoldOut — the global resting state when every slot is empty, reached from Idle (or after a sale empties the machine) once resetTransaction() has cleared any balance. Because it is reached only when there is no active transaction, escrow is empty and there is nothing to refund. Only restock (admin) moves it out. We treat SoldOut as a global state for the whole machine being empty, which is the cleaner interview story.

Here is the transition table — draw this on the whiteboard; it’s the highest-signal artifact you can produce. Note the SoldOut/insertCoin cell: there is no active balance, so the action is simply to return the just-inserted coin, not to “refund” a (nonexistent) transaction balance.

ACTION         | Idle             | HasMoney                  | Dispensing      | SoldOut
---------------+------------------+---------------------------+-----------------+-----------------------------
insertCoin     | escrow→HasMoney  | escrow→HasMoney           | reject (busy)   | reject coin: return it
               |                  |                           |                 |  (no active balance)
selectProduct  | error (no money) | check stock/funds/change: | reject (busy)   | error (empty)
               |                  |  ok        → Dispensing   |                 |
               |                  |  low funds → HasMoney     |                 |
               |                  |  no stock  → HasMoney     |                 |
               |                  |  no change → refund→Idle  |                 |
dispense       | error            | error (select first)      | release+change  | error
               |                  |                           |  → Idle/SoldOut |
cancel/refund  | nothing          | return escrow → Idle      | reject (busy)   | nothing (escrow empty)

Note how SoldOut/cancel is correctly “nothing”: this confirms no balance exists in SoldOut, so SoldOut/insertCoin cannot be “refund” — it can only be “return the coin you just tried to insert.”

            insertCoin
   ┌──────────────────────────┐
   │                          ▼
┌──────┐  insertCoin     ┌──────────┐  select(ok)    ┌────────────┐
│ Idle │ ───────────────▶│ HasMoney │ ──────────────▶│ Dispensing │
└──────┘                 └──────────┘                └────────────┘
   ▲                       │   ▲                            │
   │   cancel(return       │   └── select(low funds /       │
   │        escrow)        │       out of stock /           │
   └───────────────────────┘       no change: stay/refund)  │
   │                                                         │
   └───────────────── dispense done (commit + change) ◀──────┘
   │
   │  (machine empty after sale)      restock
   └────────────▶  ┌─────────┐ ◀───────────────  (admin)
                   │ SoldOut │
                   └─────────┘

Step 4 — UML class diagram

                ┌────────────────────────────────────┐
                │           VendingMachine            │  «Context»
                ├────────────────────────────────────┤
                │ - state: State                      │
                │ - inventory: Inventory              │
                │ - register: CashRegister            │
                │ - escrow: Coin[]   (this txn)       │
                │ - selectedCode: string?             │
                ├────────────────────────────────────┤
                │ + insertCoin(c: Coin)               │
                │ + selectProduct(code: string)       │
                │ + dispense()                        │
                │ + cancel()                          │
                │ + setState(s: State)                │  ◀── states call this
                │ + escrowCoin / escrowTotal          │
                │ + takeEscrow(): Coin[]              │
                │ + select / getSelected / reset      │
                └───────────────┬────────────────────┘
                                │ has-a (delegates to)
                                ▼
                       ┌──────────────────┐
                       │     «interface»  │
                       │       State      │
                       ├──────────────────┤
                       │ insertCoin(c)    │
                       │ selectProduct(x) │
                       │ dispense()       │
                       │ cancel()         │
                       └────────▲─────────┘
            ┌───────────┬───────┴───────┬──────────────┐
            │           │               │              │
     ┌───────────┐ ┌─────────────┐ ┌───────────────┐ ┌────────────┐
     │ IdleState │ │HasMoneyState│ │DispensingState│ │SoldOutState│
     └───────────┘ └─────────────┘ └───────────────┘ └────────────┘

   ┌──────────────┐        ┌────────────────────────┐   ┌──────────────┐
   │  Inventory   │        │      CashRegister      │   │   Product    │
   ├──────────────┤        ├────────────────────────┤   ├──────────────┤
   │ slots: Map   │        │ bank: Map<Coin,count>  │   │ id, name     │
   │  code→(prod, │        │ canMakeChange(amt):bool│   │ priceCents   │
   │       qty)   │        │ planChange(amt):Plan?  │   └──────────────┘
   │ getProduct(c)│        │ commit(coins[])        │
   │ hasStock(c)  │        │ dispense(plan)         │   ┌──────────────┐
   │ decrement(c) │        └────────────────────────┘   │ «enum» Coin  │
   │ restock(...) │                                      │ values: cents│
   │ isEmpty()    │                                      └──────────────┘
   └──────────────┘

Step 5 — Key method signatures: the Context and the change algorithm

The crux: every state implements the same four methods, and the context delegates blindly. The machine never asks “what state am I in?” — it just calls state.selectProduct(...). The context also owns the escrow for the current transaction.

enum Coin { PENNY = 1, NICKEL = 5, DIME = 10, QUARTER = 25, DOLLAR = 100 }

interface State {
insertCoin(coin: Coin): void;
selectProduct(code: string): void;
dispense(): void;
cancel(): void;
}

// NOTE: VendingMachine is shown before the concrete states for readability.
// new IdleState(this) / new SoldOutState(this) run at constructor *call* time,
// after the whole file is evaluated, so forward references resolve fine.
class VendingMachine {
private state!: State;
private escrow: Coin[] = [];          // coins for THIS txn, not yet in bank
private selectedCode: string | null = null;

constructor(
  readonly inventory: Inventory,
  readonly register: CashRegister,
) {
  this.state = inventory.isEmpty()
    ? new SoldOutState(this)
    : new IdleState(this);
}

// user-facing API delegates to current state
insertCoin(c: Coin) { this.state.insertCoin(c); }
selectProduct(code: string) { this.state.selectProduct(code); }
dispense() { this.state.dispense(); }
cancel() { this.state.cancel(); }

// helpers states use
setState(s: State) { this.state = s; }
escrowCoin(c: Coin) { this.escrow.push(c); }
escrowTotal() { return this.escrow.reduce((a, c) => a + c, 0); }
takeEscrow(): Coin[] { const e = this.escrow; this.escrow = []; return e; }
select(code: string) { this.selectedCode = code; }
getSelected() { return this.selectedCode; }
resetTransaction() { this.escrow = []; this.selectedCode = null; }
}

The change-making algorithm — greedy is a trap for non-canonical coin sets

canMakeChange(amount) and the dispense plan live in the CashRegister. The naive approach is greedy: take as many of the largest denomination as possible, then the next, and so on, bounded by what’s in the bank. Greedy is only correct for canonical coin systems — and US denominations (1, 5, 10, 25, 100) happen to be canonical, so greedy yields an optimal (minimal-coin) result. But for an arbitrary denomination set greedy can fail even when change is makeable.

Classic counterexample: denominations {1, 3, 4}, make 6. Greedy takes 4 + 1 + 1 = 3 coins; the optimal is 3 + 3 = 2 coins. Worse, with limited bank counts greedy can dead-end and report failure on an amount that the optimal algorithm could actually make. So greedy is not just sub-optimal — it can be wrong.

In an interview, say this: “I’ll use greedy because US coins are canonical, but I’ll note that for arbitrary denominations you need a bounded-knapsack / DP that respects per-denomination counts.” Then show the DP fallback. Crucially, planChange returns a plan (a coin multiset) — a value object — so the state that validated the plan can hand the same plan to the state that dispenses it. No recomputation, no divergence.

type ChangePlan = Map<Coin, number>;   // value object: validated == dispensed

class CashRegister {
constructor(private bank: Map<Coin, number> = new Map()) {}

private count(c: Coin) { return this.bank.get(c) ?? 0; }

// Greedy: correct & optimal ONLY for canonical sets (US 1/5/10/25/100).
// For arbitrary denominations, replace with planChangeDP below.
planChange(amount: number): ChangePlan | null {
  if (amount < 0) return null;
  const plan: ChangePlan = new Map();
  let remaining = amount;
  const denoms = [...this.bank.keys()].sort((a, b) => b - a); // high → low
  for (const d of denoms) {
    const need = Math.min(Math.floor(remaining / d), this.count(d));
    if (need > 0) { plan.set(d, need); remaining -= need * d; }
  }
  return remaining === 0 ? plan : null;     // null => cannot make change
}

canMakeChange(amount: number): boolean { return this.planChange(amount) !== null; }

// Commit escrowed coins INTO the bank (after sale is decided).
commit(coins: Coin[]) {
  for (const c of coins) this.bank.set(c, this.count(c) + 1);
}

// Physically remove a previously-validated plan from the bank.
dispense(plan: ChangePlan) {
  for (const [c, n] of plan) {
    if (this.count(c) < n) throw new Error("plan diverged from bank");
    this.bank.set(c, this.count(c) - n);
  }
}

// DP fallback for NON-canonical denominations with bounded counts.
// Returns a min-coin plan or null. O(amount * denomKinds * maxCount).
planChangeDP(amount: number): ChangePlan | null {
  const INF = Infinity;
  const best: number[] = new Array(amount + 1).fill(INF);
  const pick: (Coin | null)[] = new Array(amount + 1).fill(null);
  best[0] = 0;
  for (const [coin, avail] of this.bank) {
    for (let used = 0; used < avail; used++) {        // bounded supply
      for (let a = amount; a >= coin; a--) {
        if (best[a - coin] + 1 < best[a]) {
          best[a] = best[a - coin] + 1; pick[a] = coin;
        }
      }
    }
  }
  if (best[amount] === INF) return null;
  const plan: ChangePlan = new Map();
  let a = amount;
  while (a > 0) { const c = pick[a]!; plan.set(c, (plan.get(c) ?? 0) + 1); a -= c; }
  return plan;
}
}

Step 6 — The interesting states: where money-safety is proven

HasMoneyState is where validation lives; DispensingState is where the money-safety invariant — “never keep money without giving product or refund” — is enforced. The design auto-advances: HasMoneyState.selectProduct does setState(Dispensing) then m.dispense(). This is intentional — there is no separate “user presses dispense” step. (If an external caller did invoke dispense() afterward, it would hit DispensingState.dispense; that’s fine, but in practice dispense is internal. All the other actions in DispensingState are “busy” guards, which is why the auto-advance is safe.)

Two things make safety provable in code rather than asserted:

1. Pass the validated plan as a value object. HasMoneyState computes the ChangePlan after committing escrow into the bank (so the customer’s coins are available for their own change), validates it, stashes it, and hands the same plan to DispensingState. No recomputation → no time-of-check/time-of-use divergence.
2. Guard decrement + dispense with a rollback that refunds the full payment. In DispensingState.dispense, if stock decrement fails (e.g., a last-item race), we refund the customer’s entire committed payment and bank nothing. The escrow coins were already committed into the bank in HasMoneyState, so DispensingState must keep a reference to those exact coins and re-emit them on failure — not merely dispense the change plan. Re-emitting the original escrow coins guarantees the refund is exact and equals the price plus any overpayment, so the machine never keeps the product price after giving no product.

class IdleState implements State {
constructor(private m: VendingMachine) {}

insertCoin(c: Coin) {
  this.m.escrowCoin(c);                      // hold in escrow, NOT in bank
  this.m.setState(new HasMoneyState(this.m));
}
selectProduct(_: string) { console.log("Insert money first"); }
dispense()               { console.log("Insert money first"); }
cancel()                 { /* nothing to cancel */ }
}

class SoldOutState implements State {
constructor(private m: VendingMachine) {}

// No active transaction here => no balance. Return the just-inserted coin.
insertCoin(c: Coin)      { console.log("Sold out — returning coin", c); }
selectProduct(_: string) { console.log("Sold out"); }
dispense()               { console.log("Sold out"); }
cancel()                 { /* nothing: escrow is empty in SoldOut */ }
}

class HasMoneyState implements State {
constructor(private m: VendingMachine) {}

insertCoin(c: Coin) { this.m.escrowCoin(c); }    // accumulate in escrow

selectProduct(code: string) {
  const product = this.m.inventory.getProduct(code);
  if (!product || !this.m.inventory.hasStock(code)) {
    console.log("Out of stock"); return;                 // stay
  }
  if (this.m.escrowTotal() < product.priceCents) {
    console.log("Insufficient funds"); return;           // stay
  }
  const changeAmt = this.m.escrowTotal() - product.priceCents;

  // Commit escrow into the bank FIRST so the customer's own coins can fund
  // their own change. canMakeChange is therefore evaluated AFTER commit.
  const escrowCoins = this.m.takeEscrow();
  this.m.register.commit(escrowCoins);
  const plan = this.m.register.planChange(changeAmt);
  if (plan === null) {
    // Roll back: undo the commit by handing the escrow coins back.
    this.m.register.dispense(toPlan(escrowCoins));        // remove from bank
    console.log("Cannot make change — refunding", escrowCoins);
    this.m.resetTransaction();
    this.m.setState(new IdleState(this.m));
    return;
  }
  this.m.select(code);
  // Pass BOTH the validated change plan AND the committed escrow coins, so
  // Dispensing can refund the FULL payment if stock decrement fails.
  this.m.setState(new DispensingState(this.m, plan, escrowCoins));
  this.m.dispense();                                      // auto-advance
}

dispense()  { console.log("Select a product first"); }

cancel() {
  const coins = this.m.takeEscrow();                      // exact coins back
  console.log("Refunding escrow", coins);
  this.m.resetTransaction();
  this.m.setState(new IdleState(this.m));
}
}

function toPlan(coins: Coin[]): Map<Coin, number> {
const p = new Map<Coin, number>();
for (const c of coins) p.set(c, (p.get(c) ?? 0) + 1);
return p;
}

class DispensingState implements State {
constructor(
  private m: VendingMachine,
  private plan: Map<Coin, number>,    // validated change (overpayment) plan
  private escrowCoins: Coin[],        // the customer's full committed payment
) {}
insertCoin(_: Coin)      { console.log("Busy, dispensing"); }
selectProduct(_: string) { console.log("Busy, dispensing"); }
cancel()                 { console.log("Too late to cancel"); }

dispense() {
  const code = this.m.getSelected();
  if (code === null) { console.log("Nothing selected"); return; }
  // Escrow is already committed into the bank; plan validated post-commit.
  try {
    this.m.inventory.decrement(code);        // commit stock (may throw)
  } catch (e) {
    // Money-safety: stock failed -> refund the FULL committed payment by
    // re-emitting the exact escrow coins (price + overpayment), and bank
    // nothing. NOT this.plan, which is only the change portion — refunding
    // that alone would keep the product price while giving no product.
    console.log("Dispense failed — refunding full payment", this.escrowCoins);
    this.m.register.dispense(toPlan(this.escrowCoins));   // return everything
    this.m.resetTransaction();
    this.m.setState(this.m.inventory.isEmpty()
      ? new SoldOutState(this.m) : new IdleState(this.m));
    return;
  }
  this.m.register.dispense(this.plan);       // exact, pre-validated change
  console.log("Dispensed", code);
  this.m.resetTransaction();
  this.m.setState(this.m.inventory.isEmpty()
    ? new SoldOutState(this.m) : new IdleState(this.m));
}
}

Step 7 — Edge cases interviewers actually probe

• Exact-change failure. Customer overpays, bank can’t make the difference. We refund (escrow makes this trivial). Decide and state: reject the sale rather than keep un-refundable money.
• First-coin escrow. Covered above — the transition coin must be banked into escrow, not just summed.
• Cancel mid-transaction. With escrow, return the exact coins; no change computation needed, so it can never fail.
• Last item / machine empties. After a successful sale, transition to SoldOut only when inventory.isEmpty() and after resetTransaction() — so SoldOut always has zero escrow.
• Coin during dispense. DispensingState is “busy”; reject. (Hardware typically can’t physically accept coins mid-dispense anyway.)
• Insufficient funds then more coins. Stay in HasMoney, keep escrowing, re-select later.
• Non-canonical denominations. Greedy can be wrong; fall back to bounded-count DP. Call this out unprompted.
• TOCTOU on stock (single-user but defensive). The decrement in DispensingState is guarded with a rollback that refunds the customer’s entire committed payment (the exact escrow coins, not just the change) and banks nothing — proving the money-safety invariant instead of asserting it.

Step 8 — Which patterns naturally emerge (and why)

Step 9 — Extensibility: “what if they ask for X?”

• Card/UPI payments. Introduce PaymentStrategy with authorize(amount) / refund(amount). HasMoneyState becomes payment-agnostic; cashless skips canMakeChange entirely.
• Cart of multiple items. HasMoneyState accumulates a selection list; validate total funds and aggregate change once. Or add a CartState.
• Multiple change algorithms. ChangeStrategy interface; inject greedy (canonical) or DP (arbitrary). Already factored as planChange vs planChangeDP.
• Maintenance/restock as a state. Add MaintenanceState entered by an admin key, where normal user actions are rejected and restock/refill are allowed.
• Real concurrency (vending bank / networked). Wrap state transitions in a lock; or model the machine as an actor processing one command at a time. Mention std::mutex around the transition for the C++ build if asked.

Closing interview line: “The State pattern gives me a transition table I can test exhaustively, the escrow model makes refunds provably safe, and the change algorithm is swappable — so adding card payments or a cart doesn’t touch the core state machine.”