Design a vending machine

Insert coins. Pick an item. Get the item. Get change. The classic State-pattern interview problem — a machine with five states, well-defined transitions, and a long tail of edge cases (selected item out of stock, exact change not available, refund mid-purchase). The thing the interviewer is grading is whether you write the transitions explicitly or smear them across if statements.

1 · Clarifying questions

Payment?	Coins only for the OOD round. Card/contactless is the same shape, different state-entry actions.
Refund?	Yes — at any point before dispense, user can press cancel and get coins back.
Inventory?	Bounded; each slot has a count. When zero, the slot reports out-of-stock.
Change?	The machine tracks its own coin inventory. If it can't make exact change, it refuses the sale and returns the inserted coins.
Concurrent users?	One user at a time — the machine is a single physical resource. Concurrency is between the user and the maintenance worker.
Timeout?	Yes — if the user inserts coins and walks away, refund after N seconds.

2 · States

                          insert_coin
              ┌──────────────────────────┐
              ▼                          │
   ┌──► IDLE ────────► HAS_MONEY  ─────┘ (cumulative)
   │     ▲                │
   │     │                │ select_item
   │     │                ▼
   │     │           VALIDATING ──[invalid / out-of-stock]──► HAS_MONEY
   │     │                │
   │     │                │ [valid + sufficient]
   │     │                ▼
   │     │            DISPENSING ──► RETURNING_CHANGE ──► IDLE
   │     │
   │     │ cancel  (from HAS_MONEY)
   │     ▼
   │  RETURNING_REFUND ──► IDLE
   │
   └─ timeout (from HAS_MONEY) ──► RETURNING_REFUND

Five states. Every transition has a trigger and an action. The transition table is the design — once you draw it, the code mostly writes itself.

3 · Entities

Coin enum (PENNY, NICKEL, DIME, QUARTER, DOLLAR) with a value_cents.
Item — slot_id, name, price_cents.
Slot — item, count. Knows if it's empty.
VendingMachine — slots, coin inventory, current balance, current state.
State (abstract) → IdleState, HasMoneyState, DispensingState, ReturningChangeState, RefundingState. Each implements the transition methods; the methods that don't apply throw InvalidOperation.

4 · Class sketch (State pattern)

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

class Item:
  slot_id: str
  name: str
  price_cents: int

class Slot:
  item: Item
  count: int
  def take_one(): self.count -= 1
  def is_empty(): return self.count == 0

class State(ABC):
  def __init__(machine): self.m = machine
  def insert_coin(c):      raise InvalidOperation()
  def select_item(slot_id): raise InvalidOperation()
  def cancel():            raise InvalidOperation()
  def collect_dispensed(): raise InvalidOperation()

class IdleState(State):
  def insert_coin(c):
    self.m.balance += c.value
    self.m.transition(HasMoneyState)

class HasMoneyState(State):
  def insert_coin(c):
    self.m.balance += c.value
  def select_item(slot_id):
    slot = self.m.slot(slot_id)
    if slot.is_empty(): raise OutOfStock()
    if self.m.balance < slot.item.price_cents:
      raise InsufficientFunds(needed=slot.item.price_cents - self.m.balance)
    self.m.pending_slot = slot
    self.m.transition(DispensingState)
  def cancel():
    self.m.refund_amount = self.m.balance
    self.m.balance = 0
    self.m.transition(RefundingState)

class DispensingState(State):
  def __init__(machine):
    super().__init__(machine)
    # entry action — happens immediately on enter
    slot = machine.pending_slot
    slot.take_one()
    machine.dispensed = slot.item
    change = machine.balance - slot.item.price_cents
    machine.balance = 0
    machine.pending_slot = None
    if change > 0:
      machine.change_due = change
      machine.transition(ReturningChangeState)
    else:
      machine.transition(IdleState)
  def collect_dispensed():
    self.m.dispensed = None
    # already transitioned in __init__

class ReturningChangeState(State):
  def __init__(machine):
    super().__init__(machine)
    coins = machine.coin_inv.make_change(machine.change_due)
    if coins is None:
      # Can't make change — this should have been checked before dispense.
      # In a more careful design, this check moves earlier and prevents the sale.
      raise CannotMakeChange()
    machine.returned_coins = coins
    machine.change_due = 0
    machine.transition(IdleState)

class RefundingState(State):
  def __init__(machine):
    super().__init__(machine)
    machine.returned_coins = machine.coin_inv.refund_inserted(machine.refund_amount)
    machine.refund_amount = 0
    machine.transition(IdleState)

class VendingMachine:
  slots: dict[str, Slot]
  coin_inv: CoinInventory
  balance: int = 0
  state: State

  def __init__(slots, coin_inv):
    self.slots, self.coin_inv = slots, coin_inv
    self.state = IdleState(self)

  def transition(StateClass): self.state = StateClass(self)
  def insert_coin(c):  self.state.insert_coin(c)
  def select_item(s):  self.state.select_item(s)
  def cancel():        self.state.cancel()
  def slot(s): return self.slots[s]

The State pattern's payoff: each state owns the transitions it allows. Calling select_item in IdleState doesn't go down a chain of ifs — it throws, because IdleState didn't override that method. The transition table from §2 is enforced by the type system.

5 · Making change

The change algorithm is small but worth getting right. Greedy (take the largest denomination first) works for standard US coins; it's not guaranteed to work for arbitrary coin sets. For interview: greedy is fine, but mention the assumption.

def make_change(amount, inv: dict[Coin, int]) -> dict[Coin, int] | None:
  result = {}
  remaining = amount
  for coin in sorted(Coin, key=lambda c: -c.value):
    if remaining == 0: break
    take = min(remaining // coin.value, inv[coin])
    if take > 0:
      result[coin] = take
      remaining -= take * coin.value
  if remaining > 0:
    return None  # can't make change with this inventory
  # Commit (caller updates inventory after success)
  return result

In production, you'd also check change feasibility before entering DISPENSING — otherwise you've taken the item out of stock for a sale you can't complete. The state machine should have a CHECK_CHANGE state between HAS_MONEY and DISPENSING.

6 · Edge cases

Item goes out of stock between display and selection. Re-check at select_item; surface OutOfStock without changing state.
Insufficient funds. Stay in HAS_MONEY; tell the user how much more is needed. Don't dispense partial items.
Cannot make exact change. Refuse the sale up front (transition to refund) or refuse to accept the last coin if it would create unmakeable change.
Coin jam / dispenser jam. Hardware-level fault. Transition to OUT_OF_ORDER state. All user-facing methods throw a service-required error.
Timeout in HAS_MONEY. Auto-refund after N seconds of inactivity. Implemented as a watchdog that fires cancel().
Refund overflow. If the machine's coin inventory is too low to refund, alert maintenance and keep state pending. Don't silently swallow the money.

7 · Extensions

Card payment. Replace the coin acceptor with a payment terminal. The state machine is the same; the entry action for HAS_MONEY changes ("authorize $X on card") and the dispense action triggers a capture.
Telemetry. Every sale emits an event (item, time, payment method). Aggregates feed the restock schedule and product mix.
Maintenance mode. A separate state entered with a key. Allows reading inventory, refilling, taking offline. Locks out customer methods.
Multi-machine fleet. Each machine periodically reports inventory and faults to a central service. Routes the maintenance worker.

8 · What gets graded

Did you draw the state machine explicitly?
Did you use the State pattern (or equivalent) rather than nested ifs?
Did you address "can't make change" before dispensing, not after?
Did you handle the timeout and the jam without being prompted?

Done

← Back to the OOD hub

All seven problems live. From here, the interview hub has the timed drills and the full prep set.

OOD hub

Found this useful?