Low-Level Design: Vending Machine (OOP Design Interview)
The vending machine is a classic low-level design problem that tests State Pattern, inventory management, payment processing, and change calculation. Commonly asked at Amazon, Google, Microsoft, and other companies in LLD interviews.
Requirements Clarification
Functional Requirements
- Display available products with prices and quantities
- Accept coins and bills (quarters, dimes, nickels, dollar bills)
- Allow product selection and dispense selected item
- Calculate and return change
- Handle edge cases: out of stock, insufficient payment, exact change required
- Admin mode: restock items, collect cash, update prices
State Machine Design
The vending machine naturally fits a State pattern with four states:
IDLE → INSERT_MONEY → PRODUCT_SELECTED → DISPENSE
↑ ↓
└────────────── RETURN CHANGE ─────────────┘
IDLE: Waiting for customer
INSERT_MONEY: Money inserted, awaiting selection or more money
PRODUCT_SELECTED: Product chosen, verifying payment
DISPENSE: Dispensing product, calculating change
Core Classes
from enum import Enum
from abc import ABC, abstractmethod
from collections import defaultdict
from typing import Optional
class Coin(Enum):
NICKEL = 5 # cents
DIME = 10
QUARTER = 25
DOLLAR = 100
class Bill(Enum):
ONE = 100 # cents
FIVE = 500
TEN = 1000
class VendingMachineState(Enum):
IDLE = "IDLE"
HAS_MONEY = "HAS_MONEY"
PRODUCT_SELECTED = "PRODUCT_SELECTED"
DISPENSING = "DISPENSING"
OUT_OF_SERVICE = "OUT_OF_SERVICE"
class Product:
def __init__(self, name: str, price_cents: int, quantity: int):
self.name = name
self.price_cents = price_cents
self.quantity = quantity
self.slot_id: Optional[str] = None
def is_available(self) -> bool:
return self.quantity > 0
def dispense(self):
if not self.is_available():
raise OutOfStockError(f"{self.name} is out of stock")
self.quantity -= 1
def restock(self, count: int):
self.quantity += count
class Inventory:
def __init__(self):
self._slots: dict[str, Product] = {} # slot_id -> Product
def add_product(self, slot_id: str, product: Product):
product.slot_id = slot_id
self._slots[slot_id] = product
def get_product(self, slot_id: str) -> Optional[Product]:
return self._slots.get(slot_id)
def display(self) -> list[dict]:
return [
{
'slot': slot_id,
'name': product.name,
'price': product.price_cents / 100,
'available': product.quantity,
}
for slot_id, product in self._slots.items()
]
class CashBox:
"""Tracks coins/bills inserted and manages change calculation"""
def __init__(self, initial_change: dict[Coin, int] = None):
# Machine's coin reserve for making change
self.reserve: dict[Coin, int] = defaultdict(int)
if initial_change:
for coin, count in initial_change.items():
self.reserve[coin] = count
self.inserted_amount = 0 # cents inserted for current transaction
def insert(self, denomination: Coin | Bill) -> int:
"""Insert money, return total inserted so far"""
self.inserted_amount += denomination.value
if isinstance(denomination, Coin):
self.reserve[denomination] += 1
return self.inserted_amount
def calculate_change(self, change_amount: int) -> dict[Coin, int]:
"""
Greedy change calculation: use largest coins first.
Returns {Coin: count} or raises if exact change impossible.
"""
if change_amount == 0:
return {}
remaining = change_amount
change_given: dict[Coin, int] = defaultdict(int)
# Use coins in descending order (greedy)
for coin in sorted(Coin, key=lambda c: c.value, reverse=True):
while remaining >= coin.value and self.reserve[coin] > 0:
change_given[coin] += 1
self.reserve[coin] -= 1
remaining -= coin.value
if remaining != 0:
# Restore coins (transaction failed — can't make change)
for coin, count in change_given.items():
self.reserve[coin] += count
raise ExactChangeRequiredError(
f"Cannot make change for {change_amount}¢"
)
return dict(change_given)
def refund(self, amount: int) -> dict[Coin, int]:
"""Return inserted money to customer"""
change = self.calculate_change(amount)
self.inserted_amount = 0
return change
def collect_transaction(self, product_price: int) -> dict[Coin, int]:
"""Complete transaction: take payment, return change"""
change_amount = self.inserted_amount - product_price
change = self.calculate_change(change_amount)
self.inserted_amount = 0
return change
State Pattern Implementation
class VendingMachineStateHandler(ABC):
"""Abstract base for all state handlers"""
def __init__(self, machine: 'VendingMachine'):
self.machine = machine
@abstractmethod
def insert_money(self, amount: Coin | Bill) -> str:
pass
@abstractmethod
def select_product(self, slot_id: str) -> str:
pass
@abstractmethod
def cancel(self) -> dict:
pass
class IdleState(VendingMachineStateHandler):
def insert_money(self, amount: Coin | Bill) -> str:
total = self.machine.cash_box.insert(amount)
self.machine.set_state(VendingMachineState.HAS_MONEY)
return f"Inserted {amount.value}¢. Total: {total}¢"
def select_product(self, slot_id: str) -> str:
return "Please insert money first"
def cancel(self) -> dict:
return {} # Nothing to return
class HasMoneyState(VendingMachineStateHandler):
def insert_money(self, amount: Coin | Bill) -> str:
total = self.machine.cash_box.insert(amount)
return f"Inserted {amount.value}¢. Total: {total}¢"
def select_product(self, slot_id: str) -> str:
product = self.machine.inventory.get_product(slot_id)
if not product:
return f"Invalid slot: {slot_id}"
if not product.is_available():
return f"{product.name} is out of stock"
inserted = self.machine.cash_box.inserted_amount
if inserted dict:
"""Refund all inserted money"""
amount = self.machine.cash_box.inserted_amount
change = self.machine.cash_box.refund(amount)
self.machine.set_state(VendingMachineState.IDLE)
return change
class ProductSelectedState(VendingMachineStateHandler):
def insert_money(self, amount) -> str:
return "Product already selected, processing..."
def select_product(self, slot_id: str) -> str:
return "Processing current selection..."
def cancel(self) -> dict:
self.machine.selected_product = None
amount = self.machine.cash_box.inserted_amount
change = self.machine.cash_box.refund(amount)
self.machine.set_state(VendingMachineState.IDLE)
return change
Main VendingMachine Class
class VendingMachine:
def __init__(self):
self.inventory = Inventory()
self.cash_box = CashBox(initial_change={
Coin.QUARTER: 20,
Coin.DIME: 20,
Coin.NICKEL: 20,
})
self.selected_product: Optional[Product] = None
self._state = VendingMachineState.IDLE
self._state_handlers = {
VendingMachineState.IDLE: IdleState(self),
VendingMachineState.HAS_MONEY: HasMoneyState(self),
VendingMachineState.PRODUCT_SELECTED: ProductSelectedState(self),
}
@property
def current_state(self) -> VendingMachineStateHandler:
return self._state_handlers[self._state]
def set_state(self, state: VendingMachineState):
self._state = state
def insert_money(self, amount: Coin | Bill) -> str:
return self.current_state.insert_money(amount)
def select_product(self, slot_id: str) -> str:
return self.current_state.select_product(slot_id)
def cancel(self) -> dict:
return self.current_state.cancel()
def dispense(self) -> str:
"""Called internally after product selection validated"""
product = self.selected_product
try:
change = self.cash_box.collect_transaction(product.price_cents)
product.dispense()
self.selected_product = None
self.set_state(VendingMachineState.IDLE)
change_str = ', '.join(f"{count}x {coin.name}"
for coin, count in change.items()) if change else "No change"
return f"Dispensed {product.name}. Change: {change_str}"
except ExactChangeRequiredError as e:
self.set_state(VendingMachineState.HAS_MONEY)
return f"Error: {e}. Please use exact change or cancel."
def display_products(self) -> list[dict]:
return self.inventory.display()
# Admin operations
def restock(self, slot_id: str, count: int):
product = self.inventory.get_product(slot_id)
if product:
product.restock(count)
def collect_cash(self) -> int:
"""Admin collects cash, leaves minimum change reserve"""
# In real system: this would transfer cash to safe and reset reserve
return sum(coin.value * count
for coin, count in self.cash_box.reserve.items())
# Custom exceptions
class OutOfStockError(Exception): pass
class ExactChangeRequiredError(Exception): pass
class InsufficientFundsError(Exception): pass
# Usage
machine = VendingMachine()
machine.inventory.add_product("A1", Product("Coca-Cola", 150, 5))
machine.inventory.add_product("A2", Product("Chips", 100, 3))
machine.inventory.add_product("B1", Product("Water", 75, 10))
print(machine.insert_money(Coin.QUARTER)) # "Inserted 25¢. Total: 25¢"
print(machine.insert_money(Coin.QUARTER)) # "Inserted 25¢. Total: 50¢"
print(machine.insert_money(Bill.ONE)) # "Inserted 100¢. Total: 150¢"
print(machine.select_product("A1")) # "Dispensed Coca-Cola. Change: No change"
print(machine.display_products())
Design Patterns Summary
- State Pattern: Each machine state has its own handler class — clean separation, easy to add new states (MAINTENANCE, EXACT_CHANGE_ONLY)
- Strategy Pattern: Change calculation algorithm is interchangeable (greedy, DP for optimal)
- Facade Pattern: VendingMachine class is the single interface — hides Inventory, CashBox, StateHandlers
- Command Pattern: Button presses (insert_money, select_product) could be Command objects for logging/audit trail
Interview Tips
- Always start with state diagram — interviewers love seeing you identify the 4 states first
- Discuss edge cases: what if machine runs out of change? (EXACT_CHANGE_ONLY state)
- Mention that greedy change doesn’t always work (e.g., coins [1, 3, 4], change 6 → greedy gives 4+1+1=3 coins but optimal is 3+3=2). For interview: mention DP is more correct, greedy is simpler.
- Extension: networked vending machines (remote inventory management), cashless payment (NFC)