Design a vending machine

01The design, in the six-step framework

1. Requirements and use cases

A vending machine is the standard first state-machine question. The point is to show that behaviour depends on a mode and that money and stock are kept honest.

• A buyer selects a product by slot code and sees its price.
• A buyer inserts coins or notes; the machine tracks the balance.
• The machine dispenses when the balance covers the price and stock exists, and returns change in available coins.
• A buyer cancels and gets the inserted money back.
• An operator restocks products and refills coins.

Out of scope: card payments, multiple simultaneous buyers and telemetry. Non-functional constraints: an operation is only legal in the right state; a new payment type or a new state must not spread conditionals through the code; change is computed before anything is dispensed.

2. Core entities and relationships

• VendingMachine: owns the inventory, the coin box, the current selection and balance, and the current state.
• State: Idle, HasSelection, HasMoney, Dispensing, each a class with the four operations.
• Inventory: slot code to product and count.
• Product: immutable name and price.
• Coin: an enum of denominations with values.
• CoinBox: counts per denomination and a change calculator.

The machine composes its inventory and coin box; states are shared stateless objects it points to. Products are values, so the inventory can hold the same product in two slots.

3. Interfaces and key methods

class State(Protocol):
    def select(self, vm: "VendingMachine", code: str) -> None: ...
    def insert(self, vm: "VendingMachine", coin: Coin) -> None: ...
    def dispense(self, vm: "VendingMachine") -> tuple[Product, dict[Coin, int]]: ...
    def cancel(self, vm: "VendingMachine") -> dict[Coin, int]: ...

class CoinBox:
    def add(self, coin: Coin) -> None: ...
    def make_change(self, amount: int) -> Optional[dict[Coin, int]]:
        """Plan change from available coins, largest first with backtracking; None if impossible. Does not deduct."""
    def take(self, plan: dict[Coin, int]) -> None: ...

class Inventory:
    def price(self, code: str) -> int: ...             # raises UnknownProduct
    def available(self, code: str) -> bool: ...
    def take(self, code: str) -> Product: ...          # raises OutOfStock

class VendingMachine:
    def select(self, code: str) -> None: ...
    def insert(self, coin: Coin) -> None: ...
    def dispense(self) -> tuple[Product, dict[Coin, int]]: ...
    def cancel(self) -> dict[Coin, int]: ...

Invariants: balance equals the value of coins inserted this session; the coin box count never goes negative; a product is removed from inventory only after change has been planned successfully.

4. Design patterns and the choices behind them

State classes

Each of the four operations behaves differently in each of the four modes: sixteen cells. The State pattern puts each row in one class and makes the illegal cells one-line refusals. Interviewers from several prep sites specifically contrast this with a tangle of booleans; the booleans version has 2^k combinations and no name for most of them.

Coins as an enum, products as values

Denominations are a closed set with a value each, so an enum is right; a class per coin would be ceremony. Products vary in data, not behaviour, so a frozen dataclass does the job and a hierarchy would be over-engineering.

Plan change, then act

Change is computed as a plan and only then are the product and coins taken. This ordering is what keeps the machine consistent when change cannot be made: the buyer gets a refusal, not a product with no change. It is the same plan-then-commit shape as the ATM dispenser.

Typed errors

Unknown product, out of stock, insufficient balance, cannot make change and illegal operation are separate exceptions so the display can say the right thing, per the validate at the boundary rule, and the use-case list from requirements maps one-to-one to the public methods.

5. Core flow and code

1. select("A1") in Idle checks the slot exists and has stock, stores the selection and moves to HasSelection.
2. insert(coin) adds to the balance; once the balance covers the price the state becomes HasMoney.
3. dispense() in HasMoney plans change for balance - price; if impossible it raises and stays put; otherwise it takes the product, deducts coins, resets the session and returns to Idle.
4. cancel() returns the inserted coins and resets.

from __future__ import annotations
from dataclasses import dataclass, field
from enum import Enum
from typing import Optional, Protocol


class IllegalOperation(Exception): ...
class UnknownProduct(Exception): ...
class OutOfStock(Exception): ...
class InsufficientBalance(Exception): ...
class CannotMakeChange(Exception): ...


class Coin(Enum):
    ONE = 1
    TWO = 2
    FIVE = 5
    TEN = 10
    TWENTY = 20


@dataclass(frozen=True)
class Product:
    name: str
    price: int


class Inventory:
    def __init__(self) -> None:
        self.slots: dict[str, tuple[Product, int]] = {}

    def restock(self, code: str, product: Product, n: int) -> None:
        _, have = self.slots.get(code, (product, 0))
        self.slots[code] = (product, have + n)

    def price(self, code: str) -> int:
        if code not in self.slots:
            raise UnknownProduct(code)
        return self.slots[code][0].price

    def available(self, code: str) -> bool:
        return code in self.slots and self.slots[code][1] > 0

    def take(self, code: str) -> Product:
        product, n = self.slots[code]
        if n == 0:
            raise OutOfStock(code)
        self.slots[code] = (product, n - 1)
        return product


class CoinBox:
    def __init__(self) -> None:
        self.counts: dict[Coin, int] = {c: 0 for c in Coin}

    def add(self, coin: Coin) -> None:
        self.counts[coin] += 1

    def make_change(self, amount: int) -> Optional[dict[Coin, int]]:
        coins = sorted(Coin, key=lambda c: -c.value)
        def go(i: int, left: int) -> Optional[dict[Coin, int]]:
            if left == 0:
                return {}
            if i == len(coins):
                return None
            c = coins[i]
            for use in range(min(self.counts[c], left // c.value), -1, -1):
                rest = go(i + 1, left - use * c.value)
                if rest is not None:
                    return ({c: use} if use else {}) | rest
            return None
        return go(0, amount)

    def take(self, plan: dict[Coin, int]) -> None:
        for c, n in plan.items():
            self.counts[c] -= n


class State(Protocol):
    def select(self, vm: VendingMachine, code: str) -> None: ...
    def insert(self, vm: VendingMachine, coin: Coin) -> None: ...
    def dispense(self, vm: VendingMachine) -> tuple[Product, dict[Coin, int]]: ...
    def cancel(self, vm: VendingMachine) -> dict[Coin, int]: ...


class Idle:
    def select(self, vm: VendingMachine, code: str) -> None:
        vm.inventory.price(code)
        if not vm.inventory.available(code):
            raise OutOfStock(code)
        vm.selection = code
        vm.state = HasSelection()
    def insert(self, vm: VendingMachine, coin: Coin) -> None: raise IllegalOperation("select a product first")
    def dispense(self, vm: VendingMachine) -> tuple[Product, dict[Coin, int]]: raise IllegalOperation("nothing selected")
    def cancel(self, vm: VendingMachine) -> dict[Coin, int]: return {}


class HasSelection:
    def select(self, vm: VendingMachine, code: str) -> None:
        Idle().select(vm, code)             # re-selecting is allowed before money goes in
    def insert(self, vm: VendingMachine, coin: Coin) -> None:
        vm.inserted.append(coin)
        vm.balance += coin.value
        if vm.balance >= vm.inventory.price(vm.selection):
            vm.state = HasMoney()
    def dispense(self, vm: VendingMachine) -> tuple[Product, dict[Coin, int]]: raise InsufficientBalance()
    def cancel(self, vm: VendingMachine) -> dict[Coin, int]: return vm.reset()


class HasMoney:
    def select(self, vm: VendingMachine, code: str) -> None: raise IllegalOperation("cancel first")
    def insert(self, vm: VendingMachine, coin: Coin) -> None:
        vm.inserted.append(coin); vm.balance += coin.value
    def dispense(self, vm: VendingMachine) -> tuple[Product, dict[Coin, int]]:
        price = vm.inventory.price(vm.selection)
        for c in vm.inserted:               # inserted coins are available for change
            vm.coin_box.add(c)
        plan = vm.coin_box.make_change(vm.balance - price)
        if plan is None:
            for c in vm.inserted:
                vm.coin_box.counts[c] -= 1
            raise CannotMakeChange()
        product = vm.inventory.take(vm.selection)
        vm.coin_box.take(plan)
        vm.inserted.clear(); vm.balance = 0; vm.selection = None
        vm.state = Idle()
        return product, plan
    def cancel(self, vm: VendingMachine) -> dict[Coin, int]: return vm.reset()


class VendingMachine:
    def __init__(self, inventory: Inventory, coin_box: CoinBox) -> None:
        self.inventory, self.coin_box = inventory, coin_box
        self.state: State = Idle()
        self.selection: Optional[str] = None
        self.balance = 0
        self.inserted: list[Coin] = []

    def reset(self) -> dict[Coin, int]:
        refund: dict[Coin, int] = {}
        for c in self.inserted:
            refund[c] = refund.get(c, 0) + 1
        self.inserted.clear(); self.balance = 0; self.selection = None
        self.state = Idle()
        return refund

    def select(self, code: str) -> None: self.state.select(self, code)
    def insert(self, coin: Coin) -> None: self.state.insert(self, coin)
    def dispense(self) -> tuple[Product, dict[Coin, int]]: return self.state.dispense(self)
    def cancel(self) -> dict[Coin, int]: return self.state.cancel(self)

6. Extensions, concurrency and what interviewers probe

• Card payments: a PaymentMethod interface with a Cash implementation holding the coin logic and a Card implementation that authorises the exact price; HasMoney stops caring where the balance came from.
• Exact change only mode is a check in select that the coin box can make change for the likeliest overpayments, or simply a flag that makes dispense refuse when the plan fails. Interviewers ask it to see whether the plan-then-commit order is deliberate.
• A new state such as OutOfService is one more class; no existing class changes. That is the whole argument for the pattern and worth saying in one sentence.
• Concurrency: one machine, one buyer, so no locks on the session; a restock from the operator while a session is open is the only race, and a lock around Inventory covers it.
• Test first: insert 20 for a 15 product with only two 2-coins in the box raises CannotMakeChange and returns the state unchanged; cancel after inserting 5 and 2 returns exactly those coins; dispense twice on a single-stock slot raises OutOfStock on the second select.
• Common mistake: computing change by greedy largest-coin without backtracking, which fails on 20 to be split with coins {10:0, 5:1, 2:10}.
• Level expectations: at L3 a correct state table and honest change calculation are enough; the follow-ups above (card payments, exact-change mode, a new state) are where an L4 candidate shows that the design absorbs change by adding classes rather than editing the machine. Keep the public API at four methods throughout; every extension lives behind them.

02Where this question was reported

• Educative · Grokking LLD chapter 11
• DesignGurus · DesignGurus case study
• ByteByteGo · ByteByteGo OOD chapter 7
• LLD Mastery · Google-tagged (Easy); state machine, change calculation
• LLD Mastery · Google-tagged with Amazon/Microsoft/Apple; State pattern, inventory
• LLD Canvas · Google-tagged (also Microsoft, Amazon); State pattern with common interface
• interviewkickstart.com · Interview Kickstart Google list: 'How do you design a vending machine in Java?'
• Exponent / Aced · Exponent/Aced course has a 'Design a Vending Machine' video lesson (premium)
• Codemia · Codemia Easy
• GitHub · awesome-low-level-design, Easy
• systemdesign.academy · systemdesign.academy solved
• javarevisited.blogspot.com · javarevisited: coins, selection, refunds, supplier reset