Courses › Low-Level Design › Problem Walkthroughs

Design a Vending Machine

The State pattern, integer money, change-making and all-or-nothing sales.

The vending machine is the textbook question for the State pattern. The same button does different things depending on whether the machine is idle, has money in it, or is out of stock. Interviewers use it to see whether you replace a tangle of if state == … checks with objects that each own one state's behavior.

Clarify the requirements

  • Products sit in slots with a price and a quantity.
  • The user inserts coins or notes, selects a product, and receives the product and their change.
  • The user can cancel at any point and get a refund.
  • An operator can restock and collect cash.
  • Out of scope unless asked: card payments, a network connection, a UI.

Questions worth asking: Do we select first or pay first? (This walkthrough uses pay first.) What if the machine can't make change? Can a user buy several items in one session?

Entities

Coin (Enum)          PENNY=1, NICKEL=5, DIME=10, QUARTER=25, DOLLAR=100  (values in cents)
Product              name, price
Slot                 code ("A1"), product, quantity
Inventory            slots by code; get(code), dispense(code), restock(code, n)
CoinBox              coin counts; add(coins), make_change(amount) -> list[Coin] | None
VendingMachine       state, balance, inserted coins; insert(coin), select(code), cancel()
State (interface)    insert(machine, coin), select(machine, code), cancel(machine)
  IdleState, HasMoneyState, OutOfServiceState

States and transitions

(Idle) -> [insert coin] -> (Has money) -> [select: enough money and in stock] -> [dispense + change] -> (Idle)
(Has money) -> [cancel] -> [refund] -> (Idle)
(Has money) -> [select: too little money / sold out] -> (Has money)

Implementation

from enum import Enum


class Coin(Enum):
    NICKEL = 5
    DIME = 10
    QUARTER = 25
    DOLLAR = 100


class VendingError(Exception):
    pass


class Slot:
    def __init__(self, code, name, price, quantity=0):
        self.code, self.name, self.price, self.quantity = code, name, price, quantity


class CoinBox:
    def __init__(self):
        self.counts = {c: 0 for c in Coin}

    def add(self, coins):
        for c in coins:
            self.counts[c] += 1

    def make_change(self, amount):
        """Greedy largest-first; works for these US denominations. None if impossible."""
        change, remaining = [], amount
        for coin in sorted(Coin, key=lambda c: -c.value):
            use = min(self.counts[coin], remaining // coin.value)
            change += [coin] * use
            remaining -= use * coin.value
        if remaining:
            return None
        for c in change:
            self.counts[c] -= 1
        return change


class State:
    def insert(self, m, coin): raise VendingError("cannot insert now")
    def select(self, m, code): raise VendingError("insert money first")
    def cancel(self, m): return []


class IdleState(State):
    def insert(self, m, coin):
        m.inserted.append(coin)
        m.state = HasMoneyState()


class HasMoneyState(State):
    def insert(self, m, coin):
        m.inserted.append(coin)

    def select(self, m, code):
        slot = m.slots.get(code)
        if slot is None:
            raise VendingError(f"no slot {code}")
        if slot.quantity == 0:
            raise VendingError(f"{slot.name} is sold out")
        paid = sum(c.value for c in m.inserted)
        if paid < slot.price:
            raise VendingError(f"insert {slot.price - paid} more cents")
        m.coin_box.add(m.inserted)               # coins can now be used for change
        change = m.coin_box.make_change(paid - slot.price)
        if change is None:                       # roll back: take the inserted coins back out
            for c in m.inserted:
                m.coin_box.counts[c] -= 1
            raise VendingError("cannot make change, please use exact amount")
        slot.quantity -= 1
        m.inserted = []
        m.state = IdleState()
        return slot.name, change

    def cancel(self, m):
        refund, m.inserted = m.inserted, []
        m.state = IdleState()
        return refund


class OutOfServiceState(State):
    def insert(self, m, coin): raise VendingError("out of service")
    def select(self, m, code): raise VendingError("out of service")


class VendingMachine:
    def __init__(self, slots):
        self.slots = {s.code: s for s in slots}
        self.coin_box = CoinBox()
        self.inserted = []
        self.state = IdleState()

    # The public API just delegates to the current state.
    def insert(self, coin): self.state.insert(self, coin)
    def select(self, code): return self.state.select(self, code)
    def cancel(self): return self.state.cancel(self)

    def set_out_of_service(self, flag):
        if self.inserted:
            raise VendingError("finish the current session first")
        self.state = OutOfServiceState() if flag else IdleState()

    def restock(self, code, n):
        self.slots[code].quantity += n

A short demo shows the whole flow:

vm = VendingMachine([Slot("A1", "Chips", 65, quantity=2)])
vm.coin_box.add([Coin.QUARTER] * 2 + [Coin.DIME] * 5)
vm.insert(Coin.DOLLAR)
assert vm.select("A1") == ("Chips", [Coin.QUARTER, Coin.DIME])

Design decisions to explain

  • Why the State pattern? Each state's rules live in one class, and adding a state (MaintenanceState, AwaitingCardState) doesn't touch the others. With if/elif on a status field, every method grows a branch for every state.
  • Money in integer cents, never floats.
  • Change-making as a separate concern. Greedy works for standard coin systems. For arbitrary denominations it can fail. See Greedy. Mention bounded coin-change DP as the general fix.
  • All-or-nothing: if change can't be made, the sale doesn't happen and the user is refunded. Never dispense a product without settling the money.

[!INTERVIEW] Where should the transition logic live? In this design each state sets m.state itself. The alternative is a transition table in the machine. Both are fine. Say which one you chose and why: self-transitioning states keep each state's rules together, while a table makes the full state graph visible in one place.

Follow-ups

  • Card payments: add a PaymentMethod strategy, CashPayment and CardPayment, and an AwaitingAuthorization state.
  • Select first, then pay: add a ProductSelectedState that remembers the slot and waits for the full amount.
  • Concurrency: a physical machine serves one user at a time. If the machine is controlled remotely, wrap the public methods in one lock.
  • Reporting: publish SaleCompleted events to an observer that tracks revenue and sends low-stock alerts.

[!TIP] Practice Design a Vending Machine · Design an ATM · Design Patterns