What you will learn
- How to recognise a state-machine problem and model it with the State pattern.
- Coin handling, change-making and refunds without invalid states.
- The edge cases interviewers probe.
Requirements
- Products in slots with a code (A1, B1), price and count.
- Accept coins of fixed denominations; reject others.
- Select a product: dispense it if paid enough and in stock, return change.
- Cancel returns the inserted money.
- When everything is sold out, refuse new money.
- If exact change can’t be made, don’t dispense (and don’t keep the money silently).
Spot the state machine
The same button means different things depending on the situation: “select” before inserting money should prompt for money; after inserting money it should try to dispense. That’s the signal for the State pattern.
insert select (ok, stock left)
Idle ----------> HasMoney --------------------------> Idle
| ^ insert (add to balance)
| |
| cancel (refund) ---------------> Idle
select (ok, last item) ----------> SoldOut
The code
"""Vending machine low-level design with the State pattern."""
from abc import ABC, abstractmethod
from dataclasses import dataclass
COINS = (1, 2, 5, 10, 20) # accepted denominations (rupees)
@dataclass
class Slot:
code: str
name: str
price: int
count: int
class State(ABC):
def __init__(self, vm: "VendingMachine"):
self.vm = vm
@abstractmethod
def insert(self, coin: int) -> str: ...
@abstractmethod
def select(self, code: str) -> str: ...
def cancel(self) -> str:
return "nothing to cancel"
class Idle(State):
def insert(self, coin):
self.vm.balance += coin
self.vm.state = HasMoney(self.vm)
return f"balance {self.vm.balance}"
def select(self, code):
return "insert money first"
class HasMoney(State):
def insert(self, coin):
self.vm.balance += coin
return f"balance {self.vm.balance}"
def select(self, code):
slot = self.vm.slots.get(code)
if slot is None:
return "invalid code"
if slot.count == 0:
return f"{slot.name} sold out"
if self.vm.balance < slot.price:
return f"need {slot.price - self.vm.balance} more"
change = self.vm.make_change(self.vm.balance - slot.price)
if change is None:
return "cannot make change, insert exact amount or cancel"
slot.count -= 1
self.vm.balance = 0
self.vm.state = Idle(self.vm) if any(s.count for s in self.vm.slots.values()) else SoldOut(self.vm)
return f"dispensed {slot.name}, change {change}"
def cancel(self):
refund = self.vm.make_change(self.vm.balance) or []
self.vm.balance = 0
self.vm.state = Idle(self.vm)
return f"refunded {refund}"
class SoldOut(State):
def insert(self, coin):
return f"sold out, returning {coin}"
def select(self, code):
return "sold out"
class VendingMachine:
def __init__(self, slots, coin_box):
self.slots = {s.code: s for s in slots}
self.coin_box = dict(coin_box) # denomination -> count available for change
self.balance = 0
self.state: State = Idle(self)
def insert(self, coin):
if coin not in COINS:
return f"rejected coin {coin}"
if isinstance(self.state, SoldOut):
return self.state.insert(coin) # handed straight back, never enters the box
self.coin_box[coin] = self.coin_box.get(coin, 0) + 1
return self.state.insert(coin)
def select(self, code):
return self.state.select(code)
def cancel(self):
return self.state.cancel()
def make_change(self, amount):
"""Greedy change from the coin box; returns list of coins or None if impossible."""
out, box = [], dict(self.coin_box)
for coin in sorted(box, reverse=True):
while amount >= coin and box[coin] > 0:
amount -= coin
box[coin] -= 1
out.append(coin)
if amount:
return None
self.coin_box = box
return out
if __name__ == "__main__":
vm = VendingMachine([Slot("A1", "Chips", 20, 1), Slot("B1", "Juice", 35, 0)], {5: 2, 1: 3})
print(vm.select("A1"))
print(vm.insert(10), "|", vm.insert(20))
print(vm.select("B1"))
print(vm.select("A1"))
print(vm.insert(10))
print(type(vm.state).__name__)
Output:
insert money first
balance 10 | balance 30
Juice sold out
dispensed Chips, change [10]
sold out, returning 10
SoldOut
Notes:
- Each state handles
insert,selectandcancelits own way;VendingMachinejust delegates. Noif state == ...chains. - Inserted coins go into the coin box, so they can be used as change later. In the run, the Rs 10 coin inserted earlier comes back as change.
make_changeworks on a copy of the coin box and commits only on success, so a failed attempt never loses coins.- In
SoldOut, a coin is handed straight back and never added to the box. (An early draft of this code counted it into the box first; it’s an easy bug to write, and exactly what a test should catch.)
About greedy change
Greedy (largest coin first) is optimal for Indian and most real coin systems, but not for arbitrary denominations. With coins 4 and amount 6, greedy gives 4+1+1 while 3+3 is better; and with a limited coin box, greedy can fail even when a combination exists. A dynamic-programming change-maker fixes both, at more cost. Mention this trade-off in interviews.
Extensions
- Admin/maintenance state for restocking and collecting cash (another State class).
- Card and UPI payments: a
PaymentMethodstrategy; the balance comes from an authorised amount. - Concurrency: a physical machine handles one customer at a time; a networked one needs a lock around select-and-dispense.
- Inventory alerts: an observer notifies the operator when a slot drops below a threshold.
Key takeaways
- When the same action means different things in different situations, use the State pattern.
- Commit side effects (coin box, stock) only after every check has passed.
- Greedy change-making is fine for canonical coin systems; know when it fails.
- Test edge cases: sold out, insufficient change, invalid coins, cancel.
Exercises
- Add a
Maintenancestate withrestock(code, n)andcollect_cash(). - Replace greedy
make_changewith a dynamic-programming version that respects coin counts. - Write tests for: invalid coin, cancel with balance, and “cannot make change”.
Quiz
- What signals that a problem should use the State pattern?
- Why does
make_changework on a copy of the coin box? - Give a coin set where greedy change-making isn’t optimal.
Show answers
- The same operation behaves differently depending on the current situation, and transitions between situations follow rules.
- So a failed attempt doesn’t remove coins; the box is updated only when exact change is possible.
- 4 for amount 6: greedy gives 4+1+1 (three coins), optimal is 3+3 (two coins).