Vending Machine
medium · state machine, exact change from a limited coin pool
Brief-reported interview attribution (unverified): Amazon, Microsoft
How to approach an LLD roundRequirements
- Functional: stock products by code, accept only valid coins, refuse insufficient funds, dispense exact change from a limited coin pool, refund on cancel, restock.
- Non-functional: change must be exact — a greedy choice is wrong when the pool lacks the right coins, so change is found by search; a failed sale must leave the inserted money untouched.
- Out of scope: card payments, product expiry, temperature control.
Statement
Design a vending machine. Prices and money are integer cents.
Coins are 1, 5, 10, 25, 100. The machine holds a coin inventory and product
quantities. A purchase takes the inserted coins into the inventory, dispenses the
product, and returns change made from the coin pool. If exact change cannot be
made, the purchase fails and the inserted money stays in the machine (the user
cancels to get it back).
class VendingMachine:
def __init__(self, coin_inventory=None):
# coin_inventory: {denomination: count}
def add_product(self, code, name, price_cents, quantity):
def restock(self, code, quantity):
def insert_coin(self, denomination):
# -> True if the coin is accepted, False for an invalid denomination
def inserted_total(self):
# -> total cents currently inserted
def cancel(self):
# -> refunded amount (cents); resets the inserted coins to zero
def select(self, code):
# -> ("ok", {"product": name, "change": {denom: count}})
# or ("error", reason): "invalid selection", "out of stock",
# "insufficient funds", "cannot make change"Rules. select checks, in order: the product exists, it is in stock, enough
money is inserted, and change can be made from the inventory plus the inserted
coins. Only then does it commit (coins in, change out, quantity down). Change must
be *exact* change: a greedy pass is not enough, because with limited coins the
greedy choice can fail while a solution exists (e.g. 30¢ from three dimes when a
quarter is also present) — search the denomination counts. cancel returns the
inserted total and resets it. An invalid coin is rejected without side effects.
Money units: all prices, coins and change are integer cents.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Product (price and stock; SRP). CoinBox (inventory + inserted coins; SRP). ChangeMaker (ABC interface) + SearchChangeMaker (exact change by search; OCP — a greedy maker swaps in). VendingMachine orchestrates and takes the change maker as a constructor argument (DIP). Pattern: Strategy (change making).
Pass an optional change_maker to the constructor to replace the change-search policy.
Public demo
# Public demo: run after implementing the class API above.
v = VendingMachine({25: 10, 10: 10, 5: 10, 1: 10})
v.add_product('A1', 'Chips', 75, 2)
v.add_product('B2', 'Soda', 100, 0)
v.add_product('C3', 'Candy', 50, 5)
print(v.select('ZZ'))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two buyers selecting at once must not sell the same last item or the same coins. The check-stock + decrement and the change computation + deduction must each be atomic — one lock per machine around select. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
The DFS change search is exponential in the worst case but the pool is tiny (5 denominations), so it is fast in practice. Extending: a PaymentMethod interface (cash/card) and a Telemetry hook for stock-out alerts.
Starter code
from abc import ABC, abstractmethod
class Product:
def __init__(self, code, name, price_cents, quantity):
"""coin_inventory: {denomination: count}"""
pass
class CoinBox:
def __init__(self, coin_inventory=None):
"""coin_inventory: {denomination: count}"""
pass
def insert(self, denomination):
"""Implement the return value and rules in the API contract."""
pass
def inserted_total(self):
"""-> total cents currently inserted"""
pass
def refund(self):
"""Implement the return value and rules in the API contract."""
pass
def change_pool(self):
"""Implement the return value and rules in the API contract."""
pass
def apply_sale(self, change):
"""Implement the return value and rules in the API contract."""
pass
class ChangeMaker(ABC):
@abstractmethod
def make_change(self, amount, available):
"""Implement the return value and rules in the API contract."""
pass
class SearchChangeMaker(ChangeMaker):
def make_change(self, amount, available):
"""Implement the return value and rules in the API contract."""
pass
class VendingMachine:
def __init__(self, coin_inventory=None, change_maker=None):
"""coin_inventory: {denomination: count}"""
pass
def add_product(self, code, name, price_cents, quantity):
"""Implement the return value and rules in the API contract."""
pass
def restock(self, code, quantity):
"""Implement the return value and rules in the API contract."""
pass
def insert_coin(self, denomination):
"""-> True if the coin is accepted, False for an invalid denomination"""
pass
def inserted_total(self):
"""-> total cents currently inserted"""
pass
def cancel(self):
"""-> refunded amount (cents); resets the inserted coins to zero"""
pass
def select(self, code):
'''-> ("ok", {"product": name, "change": {denom: count}}) or ("error", reason): "invalid selection", "out of stock", "insufficient funds", "cannot make change"'''
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter