Design a vending machine (and a coffee machine)¶
TL;DR¶
- You build a machine whose four states accept only the events legal for them, over an item source that is either a shelf of slots or a coffee bar of recipes.
- Three decisions carry the interview: State classes instead of an if-ladder, validate before you transition (a refused selection leaves the balance untouched), and change-making behind a Strategy where greedy is demonstrably wrong.
- Patterns that earn their place: State, Strategy, Decorator, Factory Method, Observer. Singleton is discussed and deliberately not used.
Problem statement¶
"Design a vending machine. It holds products in slots, each with a price and a quantity. A customer inserts coins or notes, selects a product, and gets it plus change; they can cancel and be refunded at any point before the item drops. Operators restock slots and collect cash. Handle out of stock and the case where the machine cannot make change. Then: turn it into a coffee machine that brews from recipes and supports add-ons such as an extra shot."
Requirements¶
Functional
- Slots keyed by a code, each with one product, a price and a quantity.
- Accept coins and notes; the running balance is visible to the customer.
- Select a product: validate the code, the stock, the balance and whether the change can actually be made.
- Dispense the item and return change; a purchase that jams is refunded and the item goes back on the shelf.
- Cancel at any point before dispensing and get the balance back.
- Operator actions: restock a slot, collect the cash while leaving a float.
- Out of stock and insufficient change are refusals with useful messages, not crashes.
- Coffee variant: drinks brewed from recipes against an ingredient pantry, low-level alerts, and add-ons (extra shot, extra milk, sugar) that change both price and ingredients.
Non-functional and constraints
- An event that is illegal for the current state raises a domain error naming that state; the machine never silently ignores a press.
- Money is integer cents. Never a float, and never a partially applied purchase.
- Thread-safe: the machine serves one customer at a time, and concurrent presses must not produce two dispenses.
Out of scope: card and contactless payment, the note validator's optics, telemetry back-haul, the physical bill stacker.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
| Does the machine give notes as change? | No. Notes go in, coins come out, which is why "insufficient change" is a real failure mode rather than an edge case. |
| What happens if the customer cancels after selecting? | Dispensing is the point of no return for the item; cancelling is legal only while in HasMoney. An operator taking the machine offline mid-dispense refunds and restocks. |
| Is the machine restocked while it is running? | Yes. Stock lives behind the inventory's own lock, so an operator refilling column B never blocks a customer buying from column A. |
| In what order do you validate a selection? | Code, then balance, then change feasibility, then stock. The money checks need no rollback; the reservation is the only step that mutates, so it goes last. |
| Are the coffee machine and the snack machine the same class? | Yes. Both are VendingMachine over an ItemSource; only the source differs. |
| One machine per process, so a Singleton? | No. Tests build dozens, and the demo runs two side by side. |
Core entities and relationships¶
- VendingMachine — the context: current state, balance, reservation, cash box, and the lock that serialises one customer session. Every public event is one guarded delegation.
- MachineState with
Idle,HasMoney,Dispensing,OutOfService— the four states. The base class rejects every event; each subclass overrides only the cells it accepts. - ItemSource — the seam:
price_of,reserve,restore. Implemented byInventory(slots of products) and byCoffeeBar(recipes against a pantry). - Slot and Product — one column of the machine and what is in it; Reservation is what the machine holds between
selectanddispense. - CashBox — coins (payable as change) and notes (accepted, never paid out); ChangeMaker plans the coins to hand back.
- Beverage, BasicBeverage, BeverageDecorator (
ExtraShot,ExtraMilk,Sweetened) and BeverageFactory — the coffee side: a drink is a recipe wrapped in zero or more add-ons. - IngredientInventory — the pantry, consumed all-or-nothing; MaintenanceLog — an observer of low stock on either side.
Multiplicities: machine 1 -> 1 state, machine 1 -> 1 item source, inventory 1 -> * slots, slot 1 -> 1 product, machine 1 -> 1 cash box, transaction 1 -> * coins of change.
Class diagram¶
The context, its four states, and the money.
classDiagram
class VendingMachine {
-_state: MachineState
-_balance: Money
-_reserved: Reservation
-_lock: Lock
+transitions: List~tuple~
+insert(denomination) None
+select(code: str) None
+dispense() Transaction
+cancel() Money
+take_offline() Money
+reserve(code: str) None
+release() Transaction
+refund() Money
+transition_to(state: MachineState) None
}
class MachineState {
+name: str
+insert(machine, denomination) None
+select(machine, code: str) None
+dispense(machine) Transaction
+cancel(machine) Money
+take_offline(machine) Money
+bring_online(machine) None
}
class Idle
class HasMoney
class Dispensing
class OutOfService
class CashBox {
+coins: Dict~Coin,int~
+notes: Dict~Note,int~
+add(denomination) None
+take(coins) None
+payable() Dict~Coin,int~
+total() Money
}
class Reservation {
+code: str
+item: str
+price: Money
}
class Transaction {
+id: str
+item: str
+price: Money
+change: Tuple~Coin~
+change_amount() Money
}
class ChangeMaker {
<<interface>>
+name: str
+plan(amount: Money, available: Dict~Coin,int~) Tuple~Coin~
}
class GreedyChangeMaker
class MinimalChangeMaker
class Dispenser {
<<interface>>
+eject(item: str) bool
}
class Coin {
<<enumeration>>
FIVE
TEN
QUARTER
HALF
DOLLAR
}
class Note {
<<enumeration>>
ONE
FIVE
TEN
}
MachineState <|-- Idle
MachineState <|-- HasMoney
MachineState <|-- Dispensing
MachineState <|-- OutOfService
VendingMachine o-- MachineState : current
VendingMachine *-- CashBox
VendingMachine --> Reservation
VendingMachine --> ChangeMaker
VendingMachine --> Dispenser
VendingMachine ..> Transaction : records
ChangeMaker <|.. GreedyChangeMaker
ChangeMaker <|.. MinimalChangeMaker
CashBox --> Coin
CashBox --> NoteThe two item sources: a shelf of slots, and the coffee bar with its decorated drinks.
classDiagram
class ItemSource {
<<interface>>
+price_of(code: str) Money
+reserve(code: str) str
+restore(code: str) None
}
class Inventory {
-_lock: Lock
+restock(code: str, count: int) None
+stock(code: str) int
+subscribe(listener: StockListener) None
}
class Slot {
+code: str
+quantity: int
+capacity: int
+take() str
+put_back() None
}
class Product {
+code: str
+name: str
+price: Money
}
class CoffeeBar {
+codes() List~str~
}
class IngredientInventory {
-_lock: Lock
+consume(amounts) None
+refill(ingredient: Ingredient, amount: int) None
+level(ingredient: Ingredient) int
}
class Recipe {
+name: str
+price: Money
+amounts: Dict~Ingredient,int~
}
class Beverage {
<<interface>>
+name() str
+price() Money
+ingredients() Dict~Ingredient,int~
}
class BasicBeverage
class BeverageDecorator {
<<abstract>>
+label: str
+surcharge: Money
+extra: Tuple~tuple~
}
class ExtraShot
class ExtraMilk
class Sweetened
class BeverageFactory {
+create(recipe: Recipe, add_ons) Beverage
}
class StockListener {
<<interface>>
+on_low_stock(item: str, remaining: int) None
}
class MaintenanceLog {
+lines() List~str~
}
class VendingMachine
ItemSource <|.. Inventory
ItemSource <|.. CoffeeBar
VendingMachine --> ItemSource
Inventory "1" *-- "many" Slot
Slot --> Product
CoffeeBar "1" o-- "many" Beverage
CoffeeBar --> IngredientInventory
Beverage <|.. BasicBeverage
Beverage <|.. BeverageDecorator
BeverageDecorator o-- Beverage : wraps
BeverageDecorator <|-- ExtraShot
BeverageDecorator <|-- ExtraMilk
BeverageDecorator <|-- Sweetened
BeverageFactory ..> BeverageDecorator : registry
BasicBeverage --> Recipe
StockListener <|.. MaintenanceLog
Inventory --> "many" StockListener : notifies
IngredientInventory --> "many" StockListener : notifiesDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| State | MachineState and its four subclasses |
Four statuses and six events. The base class refuses everything, so "what happens if they press dispense while idle?" is answered by a method that does not exist on Idle, not by a branch someone forgot. Adding a fifth state is one class, not an edit to every method. |
| Strategy | ChangeMaker with a greedy and a complete implementation |
Change-making is the algorithm the interviewer will poke at. Both implementations take a snapshot of the payable coins, so they are pure functions and the counterexample below is a two-line test. |
| Decorator | BeverageDecorator and the three add-ons |
Three add-ons give seven combinations as subclasses, plus a class per repeat count for "double shot". As decorators they are three classes and one stack built at wiring time. |
| Factory Method | BeverageFactory.create with its registry |
The menu becomes configuration: create(LATTE, "shot", "milk", "sugar"). A caramel syrup is a decorator class plus one registry entry, and no call site changes. |
| Observer | StockListener, implemented by MaintenanceLog |
Two publishers (slots and pantry) and one subscriber today, five subscribers tomorrow. Neither inventory knows what a maintenance log is. |
| Dependency injection | ItemSource, Dispenser, Clock, IdGenerator |
The coffee machine is this pattern's payoff: same class, different source. Tests inject a dispenser that jams. |
What was deliberately not used: Singleton. A physical machine is one object, so interviewers expect it, and it is still the wrong call — the demo runs a snack machine and a coffee machine in the same process and every test builds its own. Say that out loud. Nor did I write a factory for Product: it is a three-field record built once at wiring time, and a registry keyed by code would only duplicate the slot dictionary.
Key flows¶
A selection is four validations and one mutation. The state calls back into the machine; the machine never inspects its own state.
sequenceDiagram
autonumber
actor C as Customer
participant M as VendingMachine
participant S as HasMoney
participant I as Inventory
participant K as MinimalChangeMaker
C->>M: insert(DOLLAR)
M->>S: insert(machine, DOLLAR)
S->>M: accept, stay in HasMoney
C->>M: select(A1)
M->>S: select(machine, A1)
S->>M: reserve(A1)
M->>I: price_of(A1)
I-->>M: 1.50 USD
M->>K: plan(change due, payable coins)
alt the box can make the change
K-->>M: coins
M->>I: reserve(A1)
I-->>M: cola, held
S->>M: transition_to(Dispensing)
else the box cannot
K-->>M: InsufficientChangeError
M-->>C: refused, still HasMoney with the balance intact
endThe lifecycle. Every arrow is one overriding method; every pair of states without an arrow is a refusal.
stateDiagram-v2
[*] --> Idle
Idle --> HasMoney : first coin or note
HasMoney --> HasMoney : more money, same state
HasMoney --> Dispensing : select, after all four checks pass
HasMoney --> Idle : cancel, balance returned
Dispensing --> Idle : dispense, item and change out
Dispensing --> OutOfService : jam, refunded and put back
Dispensing --> OutOfService : operator pulls it mid-sale
HasMoney --> OutOfService : operator pulls it, refund first
Idle --> OutOfService : operator pulls it
OutOfService --> Idle : back onlineThe two arrows into OutOfService from a state that holds money are the ones candidates forget. A machine that goes offline while a customer has 2.00 in it and does not refund has stolen money, and the refund has to happen before the transition, which is exactly what a State handler makes easy to write and to read.
Implementation¶
Write the vocabulary first, then the states, then the machine that owns the data, and only then the coffee variant. The money-handling types come first because everything else refers to them.
Coins are payable and notes are not, which is the single fact that makes "insufficient change" possible. Both are IntEnum in cents, so Coin.QUARTER.money is a Money, never a float.
code/lld/vending_machine/models.py — denominations
class Coin(IntEnum):
"""What the machine accepts *and* pays out, in cents."""
FIVE = 5
TEN = 10
QUARTER = 25
HALF = 50
DOLLAR = 100
@property
def money(self) -> Money:
return Money(int(self))
class Note(IntEnum):
"""What the machine accepts but never pays out: change comes back in coins."""
ONE = 100
FIVE = 500
TEN = 1000
@property
def money(self) -> Money:
return Money(int(self))
class Ingredient(StrEnum):
WATER = "water"
BEANS = "beans"
MILK = "milk"
SUGAR = "sugar"
CHOCOLATE = "chocolate"
code/lld/vending_machine/models.py — errors
class UnknownSlotError(NotFoundError):
"""No such selection code on this machine."""
class OutOfStockError(ConflictError):
"""The slot exists but is empty."""
class OutOfIngredientError(ConflictError):
"""The coffee machine cannot brew this recipe with what is left in the pantry."""
class InsufficientFundsError(ValidationError):
"""The balance does not cover the price; the message says how much is missing."""
class InsufficientChangeError(ConflictError):
"""The cash box cannot make the change this purchase would require."""
class IllegalActionError(InvalidStateError):
"""The event is not legal in the machine's current state."""
class DispenseFailedError(ConflictError):
"""The motor did not hand the item over; the money is refunded and the stock restored."""
class SlotFullError(ValidationError):
"""A restock would put more items in the slot than it can hold."""
Slot and CashBox hold the mutable counts; Transaction and Reservation are the immutable records of what happened and what is being held.
code/lld/vending_machine/models.py — entities
@dataclass(frozen=True, slots=True)
class Product:
code: str
name: str
price: Money
@dataclass(slots=True)
class Slot:
"""One column of the machine: a product, how many are left, how many fit."""
code: str
product: Product
quantity: int
capacity: int = 10
def is_empty(self) -> bool:
return self.quantity == 0
def take(self) -> str:
if self.is_empty():
raise OutOfStockError(f"{self.product.name} is sold out")
self.quantity -= 1
return self.product.name
def put_back(self) -> None:
self.quantity = min(self.capacity, self.quantity + 1)
def restock(self, count: int) -> None:
if count < 1:
raise ValidationError("restock count must be positive")
if self.quantity + count > self.capacity:
raise SlotFullError(f"slot {self.code} holds {self.capacity}, has {self.quantity}")
self.quantity += count
@dataclass(slots=True)
class CashBox:
"""The float plus everything customers have paid in. Coins are payable, notes are not."""
coins: dict[Coin, int] = field(default_factory=dict)
notes: dict[Note, int] = field(default_factory=dict)
def add(self, denomination: Coin | Note) -> None:
target = self.coins if isinstance(denomination, Coin) else self.notes
target[denomination] = target.get(denomination, 0) + 1 # type: ignore[index]
def take(self, coins: Iterable[Coin]) -> None:
for coin in coins:
remaining = self.coins.get(coin, 0)
if remaining < 1:
raise InsufficientChangeError(f"no {coin.money} coin left in the box")
self.coins[coin] = remaining - 1
def payable(self) -> dict[Coin, int]:
"""A snapshot of the coins available for change (notes are not payable)."""
return {coin: count for coin, count in self.coins.items() if count > 0}
def total(self) -> Money:
coins = sum(int(coin) * count for coin, count in self.coins.items())
notes = sum(int(note) * count for note, count in self.notes.items())
return Money(coins + notes)
@dataclass(frozen=True, slots=True)
class Transaction:
"""One completed purchase, kept for the audit trail and the tests."""
id: str
code: str
item: str
price: Money
paid: Money
change: tuple[Coin, ...]
at: float
def change_amount(self) -> Money:
return Money(sum(int(coin) for coin in self.change))
@dataclass(frozen=True, slots=True)
class Reservation:
"""What the machine is holding for the customer between `select` and `dispense`."""
code: str
item: str
price: Money
@dataclass(frozen=True, slots=True)
class Recipe:
"""What a drink costs the pantry: millilitres of water and milk, grams of the rest."""
name: str
price: Money
amounts: Mapping[Ingredient, int] = field(default_factory=dict)
The three protocols are the seams. ItemSource is the one that turns this design into two machines.
code/lld/vending_machine/models.py — the seams
class ItemSource(Protocol):
"""Where a selection code turns into something to hand over.
A shelf of slots and a coffee bar of recipes both satisfy it, which is why the
coffee machine is the same machine with a different source injected.
"""
def price_of(self, code: str) -> Money: ...
def reserve(self, code: str) -> str: ...
def restore(self, code: str) -> None: ...
class Dispenser(Protocol):
"""The motor. Returns False when the item jams instead of dropping."""
def eject(self, item: str) -> bool: ...
class StockListener(Protocol):
"""Observer: told when a slot or an ingredient crosses its low-stock threshold."""
def on_low_stock(self, item: str, remaining: int) -> None: ...
Now the states. Read them as a table: Idle accepts money and going offline, HasMoney accepts money, selection, cancellation and going offline, Dispensing accepts dispensing and going offline, OutOfService accepts coming back. Everything else raises, and the message names the state.
code/lld/vending_machine/states.py — the four states
class MachineState:
"""Refuses everything. The refusal names the state, which is what tests assert on."""
name = "MachineState"
def insert(self, machine: VendingMachine, denomination: Coin | Note) -> None:
raise IllegalActionError(f"cannot insert money while {self.name}")
def select(self, machine: VendingMachine, code: str) -> None:
raise IllegalActionError(f"cannot select while {self.name}")
def dispense(self, machine: VendingMachine) -> Transaction:
raise IllegalActionError(f"cannot dispense while {self.name}")
def cancel(self, machine: VendingMachine) -> Money:
raise IllegalActionError(f"nothing to cancel while {self.name}")
def take_offline(self, machine: VendingMachine) -> Money:
raise IllegalActionError(f"cannot go offline while {self.name}")
def bring_online(self, machine: VendingMachine) -> None:
raise IllegalActionError(f"cannot come online while {self.name}")
class Idle(MachineState):
name = "Idle"
def insert(self, machine: VendingMachine, denomination: Coin | Note) -> None:
machine.accept(denomination)
machine.transition_to(HasMoney())
def take_offline(self, machine: VendingMachine) -> Money:
machine.transition_to(OutOfService())
return Money(0)
class HasMoney(MachineState):
name = "HasMoney"
def insert(self, machine: VendingMachine, denomination: Coin | Note) -> None:
machine.accept(denomination) # no transition: more money, same state
def select(self, machine: VendingMachine, code: str) -> None:
machine.reserve(code) # raises on unknown code, empty slot, short balance, no change
machine.transition_to(Dispensing())
def cancel(self, machine: VendingMachine) -> Money:
refund = machine.refund()
machine.transition_to(Idle())
return refund
def take_offline(self, machine: VendingMachine) -> Money:
refund = machine.refund()
machine.transition_to(OutOfService())
return refund
class Dispensing(MachineState):
name = "Dispensing"
def dispense(self, machine: VendingMachine) -> Transaction:
try:
transaction = machine.release()
except DispenseFailedError:
machine.restore() # the item goes back on the shelf
machine.refund() # and the money goes back to the customer
machine.transition_to(OutOfService())
raise
machine.transition_to(Idle())
return transaction
def take_offline(self, machine: VendingMachine) -> Money:
machine.restore()
refund = machine.refund()
machine.transition_to(OutOfService())
return refund
class OutOfService(MachineState):
name = "OutOfService"
def bring_online(self, machine: VendingMachine) -> None:
machine.transition_to(Idle())
Change-making is the algorithm worth arguing about, so it is a strategy over a snapshot of the payable coins.
code/lld/vending_machine/strategies.py — change makers
class ChangeMaker(Protocol):
"""Plans the coins to pay out. Raises when the box cannot make the amount."""
name: str
def plan(self, amount: Money, available: dict[Coin, int]) -> tuple[Coin, ...]: ...
class GreedyChangeMaker:
"""Largest coin that still fits, over and over. Fast, and incomplete.
With unlimited coins greedy is optimal for this denomination set. With a real
cash box it is not even *correct*: 30 cents from one quarter and three dimes
fails, because greedy commits to the quarter and then has no five-cent coin.
"""
name = "greedy"
def plan(self, amount: Money, available: dict[Coin, int]) -> tuple[Coin, ...]:
remaining = amount.cents
chosen: list[Coin] = []
for coin in sorted(available, reverse=True):
take = min(available[coin], remaining // int(coin))
chosen.extend([coin] * take)
remaining -= int(coin) * take
if remaining:
raise InsufficientChangeError(f"cannot make {amount} from the coins in the box")
return tuple(chosen)
class MinimalChangeMaker:
"""Fewest coins that add up, searching every count of every denomination.
Complete: it finds a combination whenever one exists. The search is memoised
on (denomination index, remaining amount), so the number of distinct
sub-problems is the number of denominations times the amount - a fixed
ceiling that does not grow with how full the cash box is.
"""
name = "minimal"
def plan(self, amount: Money, available: dict[Coin, int]) -> tuple[Coin, ...]:
denominations = sorted(available, reverse=True)
memo: dict[tuple[int, int], tuple[Coin, ...] | None] = {}
def solve(index: int, remaining: int) -> tuple[Coin, ...] | None:
if remaining == 0:
return ()
if index == len(denominations):
return None
key = (index, remaining)
if key in memo:
return memo[key]
coin = denominations[index]
best: tuple[Coin, ...] | None = None
for count in range(min(available[coin], remaining // int(coin)), -1, -1):
rest = solve(index + 1, remaining - int(coin) * count)
if rest is None:
continue
candidate = (coin,) * count + rest
if best is None or len(candidate) < len(best):
best = candidate
memo[key] = best
return best
plan = solve(0, amount.cents)
if plan is None:
raise InsufficientChangeError(f"cannot make {amount} from the coins in the box")
return plan
The inventory owns the stock and its own lock, so an operator restocking never touches the machine's lock.
code/lld/vending_machine/services.py — the shelf
class Inventory:
"""The shelf: slots behind their own lock, plus low-stock alerts.
It satisfies `ItemSource`, which is all the machine knows about it.
"""
def __init__(self, slots: Iterable[Slot], low_stock_at: int = 1) -> None:
self._slots = {slot.code: slot for slot in slots}
self._low_at = low_stock_at
self._lock = threading.Lock()
self._listeners: list[StockListener] = []
def subscribe(self, listener: StockListener) -> None:
with self._lock:
self._listeners.append(listener)
def price_of(self, code: str) -> Money:
with self._lock:
return self._slot(code).product.price
def reserve(self, code: str) -> str:
with self._lock:
slot = self._slot(code)
name = slot.take() # raises OutOfStockError while the lock is held
remaining = slot.quantity
if remaining <= self._low_at:
self._notify(f"{name} ({code})", remaining)
return name
def restore(self, code: str) -> None:
with self._lock:
self._slot(code).put_back()
def restock(self, code: str, count: int) -> None:
"""Operator refill. Takes only this lock, so a customer elsewhere is unaffected."""
with self._lock:
self._slot(code).restock(count)
def stock(self, code: str) -> int:
with self._lock:
return self._slot(code).quantity
def codes(self) -> list[str]:
with self._lock:
return sorted(self._slots)
def _slot(self, code: str) -> Slot:
try:
return self._slots[code]
except KeyError:
raise UnknownSlotError(f"no slot {code!r} on this machine") from None
def _notify(self, item: str, remaining: int) -> None:
for listener in list(self._listeners): # outside the stock lock
listener.on_low_stock(item, remaining)
The coffee variant is one more ItemSource. The pantry consumes all-or-nothing (a half-brewed latte is worse than a refusal), and every menu button is a Beverage that may be a stack of decorators.
code/lld/vending_machine/services.py — the pantry and the coffee bar
class IngredientInventory:
"""The pantry: levels in millilitres and grams, consumed all-or-nothing."""
def __init__(self, levels: Mapping[Ingredient, int], low_level_at: int = 40) -> None:
self._levels = dict(levels)
self._low_at = low_level_at
self._lock = threading.Lock()
self._listeners: list[StockListener] = []
def subscribe(self, listener: StockListener) -> None:
with self._lock:
self._listeners.append(listener)
def level(self, ingredient: Ingredient) -> int:
with self._lock:
return self._levels.get(ingredient, 0)
def consume(self, amounts: Mapping[Ingredient, int]) -> None:
"""Take every ingredient or none: a half-brewed drink is worse than a refusal."""
with self._lock:
short = [i for i, amount in amounts.items() if self._levels.get(i, 0) < amount]
if short:
names = ", ".join(sorted(i.value for i in short))
raise OutOfIngredientError(f"not enough {names}")
for ingredient, amount in amounts.items():
self._levels[ingredient] -= amount
low = [(i, self._levels[i]) for i in amounts if self._levels[i] <= self._low_at]
for ingredient, remaining in low:
self._notify(ingredient.value, remaining)
def restore(self, amounts: Mapping[Ingredient, int]) -> None:
with self._lock:
for ingredient, amount in amounts.items():
self._levels[ingredient] = self._levels.get(ingredient, 0) + amount
def refill(self, ingredient: Ingredient, amount: int) -> None:
self.restore({ingredient: amount})
def _notify(self, item: str, remaining: int) -> None:
for listener in list(self._listeners):
listener.on_low_stock(item, remaining)
class CoffeeBar:
"""An `ItemSource` over recipes instead of slots: the coffee machine in one class.
Every button is a `Beverage`, which may be a decorated one, so "latte with an
extra shot" is a menu entry rather than a class.
"""
def __init__(self, menu: Mapping[str, Beverage], pantry: IngredientInventory) -> None:
self._menu = dict(menu)
self._pantry = pantry
def price_of(self, code: str) -> Money:
return self._drink(code).price()
def reserve(self, code: str) -> str:
drink = self._drink(code)
self._pantry.consume(drink.ingredients())
return drink.name()
def restore(self, code: str) -> None:
self._pantry.restore(self._drink(code).ingredients())
def codes(self) -> list[str]:
return sorted(self._menu)
def _drink(self, code: str) -> Beverage:
try:
return self._menu[code]
except KeyError:
raise UnknownSlotError(f"no drink {code!r} on this machine") from None
code/lld/vending_machine/beverages.py — drinks, add-ons and the registry
class Beverage(Protocol):
"""What the coffee bar needs from a drink: a name, a price, a bill of ingredients."""
def name(self) -> str: ...
def price(self) -> Money: ...
def ingredients(self) -> Mapping[Ingredient, int]: ...
class BasicBeverage:
"""A drink straight from its recipe: espresso, latte, hot chocolate."""
def __init__(self, recipe: Recipe) -> None:
self._recipe = recipe
def name(self) -> str:
return self._recipe.name
def price(self) -> Money:
return self._recipe.price
def ingredients(self) -> Mapping[Ingredient, int]:
return dict(self._recipe.amounts)
class BeverageDecorator(ABC):
"""Same interface, one more responsibility. Decorators wrap decorators.
Subclasses declare three immutable class attributes; the merging logic lives
here once, so a new add-on is four lines and touches nothing else.
"""
label: str
surcharge: Money
extra: tuple[tuple[Ingredient, int], ...]
def __init__(self, drink: Beverage) -> None:
self._drink = drink
def name(self) -> str:
return f"{self._drink.name()} + {self.label}"
def price(self) -> Money:
return self._drink.price() + self.surcharge
def ingredients(self) -> Mapping[Ingredient, int]:
merged = dict(self._drink.ingredients())
for ingredient, amount in self.extra:
merged[ingredient] = merged.get(ingredient, 0) + amount
return merged
class ExtraShot(BeverageDecorator):
label = "extra shot"
surcharge = Money.of("0.50")
extra = ((Ingredient.BEANS, 7), (Ingredient.WATER, 15))
class ExtraMilk(BeverageDecorator):
label = "extra milk"
surcharge = Money.of("0.25")
extra = ((Ingredient.MILK, 50),)
class Sweetened(BeverageDecorator):
label = "sugar"
surcharge = Money(0)
extra = ((Ingredient.SUGAR, 6),)
class BeverageFactory:
"""Factory Method with a registry: a recipe plus add-on names becomes a drink.
The menu becomes configuration - `create(LATTE, "shot", "milk")` - so a new add-on is
a decorator class plus one registry entry, and no call site changes.
"""
_add_ons: dict[str, type[BeverageDecorator]] = {
"shot": ExtraShot,
"milk": ExtraMilk,
"sugar": Sweetened,
}
@classmethod
def create(cls, recipe: Recipe, *add_ons: str) -> Beverage:
drink: Beverage = BasicBeverage(recipe)
for name in add_ons:
try:
decorator = cls._add_ons[name]
except KeyError:
raise ValidationError(f"unknown add-on {name!r}") from None
drink = decorator(drink)
return drink
Finally the machine. Note the shape: six public events, each one line under the lock, then helpers that assume the lock is held. reserve is the validation order argued above; release ejects before it takes any change, so a jam cannot cost the customer money.
code/lld/vending_machine/services.py — the machine
class VendingMachine:
"""The context of the State pattern: it holds the data and serialises the events.
Each public event is one delegation under `_lock`, so check-and-transition is
atomic. The helpers below the events run with the lock already held and must
not take it again.
"""
def __init__(
self,
source: ItemSource,
cash: CashBox | None = None,
change_maker: ChangeMaker | None = None,
dispenser: Dispenser | None = None,
clock: Clock | None = None,
ids: IdGenerator | None = None,
) -> None:
self._source = source
self._cash = cash or CashBox()
self._change = change_maker or MinimalChangeMaker()
self._dispenser = dispenser or MotorDispenser()
self._clock = clock or SystemClock()
self._ids = ids or SequentialIdGenerator("TX")
self._state: MachineState = Idle()
self._balance = Money(0)
self._reserved: Reservation | None = None
self._lock = threading.Lock()
self.transitions: list[tuple[str, str]] = []
# -- events: one line each, all of them guarded ---------------------------------
def insert(self, denomination: Coin | Note) -> None:
with self._lock:
self._state.insert(self, denomination)
def select(self, code: str) -> None:
with self._lock:
self._state.select(self, code)
def dispense(self) -> Transaction:
with self._lock:
return self._state.dispense(self)
def cancel(self) -> Money:
with self._lock:
return self._state.cancel(self)
def take_offline(self) -> Money:
with self._lock:
return self._state.take_offline(self)
def bring_online(self) -> None:
with self._lock:
self._state.bring_online(self)
# -- operator -------------------------------------------------------------------
def collect_cash(self, leave: Mapping[Coin, int] | None = None) -> Money:
"""Empty the box, optionally leaving a float of coins for change."""
with self._lock:
if not self._balance.is_zero():
raise IllegalActionError("cannot collect while a customer has a balance")
total = self._cash.total()
self._cash.coins = dict(leave or {})
self._cash.notes = {}
return total - self._cash.total()
# -- reads ----------------------------------------------------------------------
def status(self) -> str:
with self._lock:
return self._state.name
def balance(self) -> Money:
with self._lock:
return self._balance
def cash_total(self) -> Money:
with self._lock:
return self._cash.total()
def payable_coins(self) -> dict[Coin, int]:
with self._lock:
return self._cash.payable()
# -- helpers: the states call these with `_lock` already held ---------------------
def accept(self, denomination: Coin | Note) -> None:
self._cash.add(denomination)
self._balance = self._balance + denomination.money
def reserve(self, code: str) -> None:
"""Validate everything that can fail, then hold the item. Order matters."""
price = self._source.price_of(code) # UnknownSlotError
if self._balance < price:
raise InsufficientFundsError(f"insert {price - self._balance} more for {code}")
change_due = self._balance - price
if not change_due.is_zero():
self._change.plan(change_due, self._cash.payable()) # InsufficientChangeError
item = self._source.reserve(code) # OutOfStockError / OutOfIngredientError
self._reserved = Reservation(code, item, price)
def restore(self) -> None:
if self._reserved is not None:
self._source.restore(self._reserved.code)
self._reserved = None
def release(self) -> Transaction:
"""Eject first: nothing is charged and no change is paid until the item is out."""
reserved = self._reserved
if reserved is None:
raise IllegalActionError("nothing is reserved")
if not self._dispenser.eject(reserved.item):
raise DispenseFailedError(f"{reserved.item} jammed on the way out")
change_due = self._balance - reserved.price
coins = () if change_due.is_zero() else self._change.plan(change_due, self._cash.payable())
self._cash.take(coins)
transaction = Transaction(
id=self._ids.next_id(),
code=reserved.code,
item=reserved.item,
price=reserved.price,
paid=self._balance,
change=coins,
at=self._clock.now(),
)
self._balance = Money(0)
self._reserved = None
return transaction
def refund(self) -> Money:
"""Give the balance back in coins. It can fail: the box may not break a note."""
if self._balance.is_zero():
return Money(0)
coins = self._change.plan(self._balance, self._cash.payable())
self._cash.take(coins)
refunded = self._balance
self._balance = Money(0)
return refunded
def transition_to(self, state: MachineState) -> None:
self.transitions.append((self._state.name, state.name))
self._state = state
Running python -m lld.vending_machine.demo drives a snack machine and then a coffee machine built from the same class:
--- snack machine: A1 cola 1.50, A2 chips 1.00, B1 juice 1.60 ---
insert 1.00 USD -> HasMoney, balance 1.00 USD
insert 0.50 USD -> HasMoney, balance 1.50 USD
select A1 -> Dispensing, cola held for this customer
dispense -> cola, change 0.00 USD, Idle
dispense again refused: cannot dispense while Idle
operator collects 2.10 USD, leaving 0.35 USD for change
select B1 with 2.00 USD refused: cannot make 0.40 USD from the coins in the box
cancel -> refunded 2.00 USD, Idle
transitions: Idle -> HasMoney -> Dispensing -> Idle -> HasMoney -> Idle
--- the same machine over recipes: C1 espresso, C2 latte with add-ons ---
select C2 (4.00 USD in) -> latte + extra shot + extra milk + sugar at 2.55 USD, change 1.45 USD
select C2 again refused: not enough beans, milk
cancel -> refunded 2.55 USD
restock A1 by 4 -> 5 in the slot
low stock: cola (A1) down to 1
low stock: beans down to 6
low stock: milk down to 30
The transitions line is worth printing in an interview: it is the state diagram as data, and asserting on it is how you prove the machine went the way you drew it.
Concurrency and edge cases¶
Which lock protects what. Two locks, one direction.
VendingMachine._lockguards the state, the balance, the reservation and the cash box. Every public event takes it, so check-and-transition is atomic: thirty-two threads racing toselectproduce exactly oneDispensingand thirty-oneIllegalActionErrors. The helpers below the events (accept,reserve,release,refund,transition_to) run with it held and must never take it again, which is why it is a plainLockrather than anRLock— the discipline is visible instead of hidden.Inventory._lock(andIngredientInventory._lock) guard stock counts.Slot.takeraisesOutOfStockErrorwhile the lock is held, so a restock cannot slip between the check and the decrement. An operator refilling a column takes only this lock; the customer at the coin slot is unaffected.
The order is always machine lock first, stock lock second. Stock objects never call back into the machine, so the order cannot invert.
Refund atomicity on a failed dispense. release ejects first and only then takes change out of the box. If the motor jams, nothing has been charged; the Dispensing state catches the failure, puts the item back on the shelf, refunds the balance and moves the machine to OutOfService before re-raising. The test asserts all four of those facts.
Greedy change is wrong, and you should say so. With unlimited coins, greedy is optimal for this denomination set. With a real cash box it is not even complete: asked for 30 cents from one quarter and three dimes, greedy takes the quarter and then needs a five-cent coin that is not there, while three dimes were sitting in the box. MinimalChangeMaker searches every count of every denomination, memoised on (denomination index, remaining amount), and returns the fewest coins. That is the difference between an answer and an answer with a counterexample.
Other edges handled: an unknown code; a slot emptied by its last sale; a balance that cannot be refunded because the box cannot break the note the customer inserted; a restock that would overflow a slot's capacity; an operator trying to collect cash while a customer has a balance; a drink whose ingredients are short, which consumes nothing.
Common mistake
Checking stock and balance inside dispense. By then the machine has already told the customer it is dispensing, and the failure has nowhere to go. Every check belongs in select, before the transition; dispense should only be able to fail on hardware, which is the one failure you cannot predict and the one that needs the refund path.
Extensibility and follow-ups¶
- Card and contactless payment: a
PaymentMethodseam next to the cash box.HasMoneybecomes reachable from an authorisation hold, andreleasecaptures instead of taking coins; the states do not change. - Dynamic pricing:
price_ofalready goes through the item source, so aPricingRulebehind it (happy hour, loyalty codes) changes one method. - Multi-select and a basket: a new state between
HasMoneyandDispensingthat accumulates reservations; the refund path becomes a loop over them, which is exactly why reservations are objects. - Telemetry:
MaintenanceLogis aStockListener; a second listener that pushes counters to a metrics endpoint subscribes alongside it and nothing else changes. - A machine that never refuses change: keep a coin float target and refuse to accept a note the box cannot break, which turns an unhappy customer into a declined note.
- Persistence and crash safety: the reservation is the piece of state that must survive a power cut; write it before ejecting and clear it after, which is the same reserve-do-commit shape as the parking lot's checkout.
Interview tip
When you draw the state diagram, write the event names on the arrows before you write any code, then implement the diagram literally: one class per state, one method per event. Interviewers grade whether the code matches the picture you drew, and this is the one problem where they can check it line by line.
Tests¶
tests/test_vending_machine.py has 24 cases. The one to walk through is the jam, because it proves the refund path; the parametrized rejection test is the one that proves "validate first, transition last":
code/lld/vending_machine/tests/test_vending_machine.py — a jammed dispense
def test_a_jam_refunds_the_customer_and_puts_the_item_back() -> None:
machine, inventory = build(dispenser=JammedDispenser())
fund(machine)
machine.select("A1")
assert inventory.stock("A1") == 1 # held for this customer
with pytest.raises(DispenseFailedError):
machine.dispense()
assert inventory.stock("A1") == 2 # back on the shelf
assert machine.balance() == Money(0) and machine.cash_total() == Money(0) # coins returned
assert machine.status() == "OutOfService"
machine.bring_online()
assert machine.status() == "Idle"
code/lld/vending_machine/tests/test_vending_machine.py — rejected selections
@pytest.mark.parametrize(
("code", "error", "message"),
[
("A1", InsufficientFundsError, "insert 0.50 USD more"),
("ZZ", UnknownSlotError, "no slot 'ZZ'"),
],
)
def test_a_rejected_selection_leaves_the_balance_and_the_stock_alone(
code: str, error: type[Exception], message: str
) -> None:
machine, inventory = build(coins={Coin.QUARTER: 4})
machine.insert(Coin.DOLLAR)
with pytest.raises(error) as exc:
machine.select(code)
assert message in str(exc.value)
assert machine.status() == "HasMoney" # validate first, transition last
assert machine.balance() == Money.of("1.00") and inventory.stock("A1") == 2
code/lld/vending_machine/tests/test_vending_machine.py — one winner
def test_thirty_two_threads_selecting_produce_exactly_one_dispense() -> None:
machine, inventory = build(coins={Coin.QUARTER: 4})
machine.insert(Coin.DOLLAR)
machine.insert(Coin.HALF)
def select(_: int) -> bool:
try:
machine.select("A1")
return True
except IllegalActionError:
return False
with ThreadPoolExecutor(max_workers=16) as pool:
results = list(pool.map(select, range(32)))
assert results.count(True) == 1 # one winner, thirty-one refusals
assert inventory.stock("A1") == 1 and machine.status() == "Dispensing"
assert machine.dispense().item == "cola"
The rest cover: a purchase with change and its transaction record; seven illegal events across all four states; an emptied slot; an unmakeable amount of change; both change makers agreeing where greedy works and disagreeing where it does not; 64 concurrent restocks conserving the count; going offline with money in the machine; the operator's collection guard; the low-stock observer; the decorator stack's price and ingredients; the factory registry; and the coffee bar refusing a drink without consuming anything. Run them with uv run pytest code/lld/vending_machine -q.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0-5 | Clarify | Notes as change? Cancel after selecting? Restock while running? Coffee variant? Out of scope: card payment, telemetry. |
| 5-10 | States | Draw the four states and every arrow. Say "the base class rejects, subclasses accept" while you draw. |
| 10-16 | Entities | Slot, Product, CashBox, Transaction, Reservation. Introduce ItemSource as the seam and name the coffee machine as its second implementation. |
| 16-32 | Code | MachineState and the four subclasses, then VendingMachine with its events and reserve. Say the validation order out loud as you write it. |
| 32-38 | Change and failure | The greedy counterexample, then the jam path: eject first, refund, restock, offline. |
| 38-45 | Coffee and extensions | CoffeeBar as an ItemSource, decorators for add-ons, then card payment and multi-select as the follow-ups. |
Related¶
- State — the four states, and the enum-plus-table alternative
- Strategy — the two change makers
- Decorator — add-ons that stack instead of subclassing
- Factory Method — the add-on registry
- Design an ATM — the same session shape with authentication and a cash cassette
- Design a parking lot — the other reserve-then-commit problem