Vending Machine

medium · state machine, exact change from a limited coin pool

Brief-reported interview attribution (unverified): Amazon, Microsoft

How to approach an LLD round

Requirements

  • 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. Rubber DuckCharacter joke · No posting date

    Quack. (Translation: have you tried printing it?)

  2. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  3. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  4. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.