vishal maurya

LLD Series: Vending Machine (Low-Level Design)

Overview

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

Typical phrasing: "Design a vending machine. A user inserts coins/notes, selects a product, the machine dispenses it and returns change. Handle sold-out items, insufficient money, cancellation and refunds."

  • Asked at: Amex, PayU, Visa, Mastercard and most product companies as the textbook State pattern problem (ATM and vending machine are siblings).
  • Interviewer is checking: states and legal transitions, rejecting invalid operations per state, the change-making logic (and "exact change only" case), inventory/cash separation, admin operations, and being able to explain why State beats flags.

2. Requirements clarification

Functional

  1. Slots (code -> product, price, quantity).
  2. Accept denominations Rs 1/2/5/10/20/50/100, one at a time.
  3. Select a product by slot code; if enough money and in stock, dispense and return change.
  4. Cancel at any time before dispense -> full refund of inserted money.
  5. Sold-out slot / invalid code / insufficient balance -> clear error, machine stays usable.
  6. Cannot give change -> reject sale (do not take the money) with "exact change only".
  7. Admin: restock products, load change coins. Machine goes OUT_OF_SERVICE when everything is sold out.

Non-functional: correctness of cash accounting; thread safety (kiosk + admin/remote monitoring); easy to add states/payment types.

Assumptions: cash only (cards/UPI mentioned as extension); one customer session at a time; whole-rupee prices; change can use coins previously inserted by the same customer.

Out of scope: hardware faults, temperature, telemetry, price changes while a session is open, remote management, persistence.

3. Entities, relationships, class diagram

 +-----------------------+ has  +-----------+ 1   * +--------+ 1  1 +---------+
 |    VendingMachine     |----->| Inventory |------>|  Slot  |----->| Product |
 | (State context)       |      +-----------+       | qty    |      | price   |
 | state: VendingState   | has  +-----------+       +--------+      +---------+
 | inserted coins        |----->|  CashBox  |  coins in machine
 +-----------+-----------+      +-----------+
             | uses                   
             v                         +--------------------+
   <<interface>> VendingState          |<<interface>>       |
   - insertMoney/selectProduct/cancel  | ChangeMaker        |<|-- GreedyChangeMaker
      ^        ^          ^        ^   +--------------------+
 IdleState HasMoneyState DispensingState OutOfServiceState

State machine:

              insertMoney                       selectProduct (ok)
   IDLE  ----------------->  HAS_MONEY  ------------------------->  DISPENSING
    ^  ^                      |  ^  |  insertMoney (self loop)           |
    |  |        cancel        |  |  +-- selectProduct (error: stay)      | done
    |  +----------------------+  +------------------------------------- +
    |                                                                    v
    +--------------------------- items left ----------------------------+
                                  all sold out -> OUT_OF_SERVICE --restock--> IDLE

4. Design patterns and why

PatternWhereWhy / rejected alternative
StateVendingState and 4 statesEach state decides what each input means. Default-reject methods mean a new state only lists what it allows. Rejected: if (hasMoney && !dispensing ...) flag soup, which explodes with each new feature.
StrategyChangeMakerGreedy now; DP / "prefer keeping small coins" later without touching states.
Facade/ContextVendingMachinePublic API for customer + admin; owns inserted coins and delegates behaviour.
Encapsulated collectionsInventory, CashBoxSale logic never touches maps directly; invariants (no negative qty) live in one place.
(Mention) Factorybuild machine from configSlots/prices from a config file.
(Mention) Observerlow stock alert to operatorListener after Slot.take().

Singleton states (INSTANCE) are fine because states are stateless; per-session data lives in the context (inserted coins). If a state needed data you would instantiate it per transition.

5. Complete Java code

Default package; javac *.java && java Main.

5.1 Basic types

// VendingException.java
public class VendingException extends RuntimeException {
    public VendingException(String m) { super(m); }
}

// Denomination.java
public enum Denomination {
    ONE(1), TWO(2), FIVE(5), TEN(10), TWENTY(20), FIFTY(50), HUNDRED(100);
    private final int value;
    Denomination(int value) { this.value = value; }
    public int value() { return value; }
}

// Product.java
public final class Product {
    private final String name; private final int price;
    public Product(String name, int price) { this.name = name; this.price = price; }
    public String name() { return name; }
    public int price() { return price; }
    @Override public String toString() { return name + "(Rs " + price + ")"; }
}

// Slot.java
public final class Slot {
    private final String code; private final Product product; private int quantity;
    public Slot(String code, Product product, int quantity) { this.code = code; this.product = product; this.quantity = quantity; }
    public String code() { return code; }
    public Product product() { return product; }
    public int quantity() { return quantity; }
    public boolean isSoldOut() { return quantity == 0; }
    void add(int n) { quantity += n; }
    void take() { if (quantity == 0) throw new VendingException("Slot empty " + code); quantity--; }
}

// Inventory.java
import java.util.*;

public final class Inventory {
    private final Map<String, Slot> slots = new TreeMap<>();

    public void addSlot(Slot s) { slots.put(s.code(), s); }
    public Slot slot(String code) {
        Slot s = slots.get(code);
        if (s == null) throw new VendingException("Invalid selection " + code);
        return s;
    }
    public void restock(String code, int qty) {
        if (qty <= 0) throw new VendingException("Invalid quantity");
        slot(code).add(qty);
    }
    public boolean allSoldOut() { return slots.values().stream().allMatch(Slot::isSoldOut); }
    public String summary() {
        StringBuilder sb = new StringBuilder();
        slots.values().forEach(s -> sb.append(s.code()).append('=').append(s.product().name()).append('x').append(s.quantity()).append(' '));
        return sb.toString().trim();
    }
}

// CashBox.java
import java.util.*;

/** Coin/note inventory of the machine. Immutable-style snapshots are used for dry-run change calculation. */
public final class CashBox {
    private final Map<Denomination, Integer> stock = new EnumMap<>(Denomination.class);

    public void add(Denomination d, int n) { stock.merge(d, n, Integer::sum); }
    public void addAll(Map<Denomination, Integer> m) { m.forEach(this::add); }
    public void remove(Map<Denomination, Integer> m) { m.forEach((d, n) -> stock.merge(d, -n, Integer::sum)); }
    public Map<Denomination, Integer> snapshot() {
        Map<Denomination, Integer> copy = new EnumMap<>(Denomination.class);
        copy.putAll(stock);
        return copy;
    }
    public long total() { return stock.entrySet().stream().mapToLong(e -> (long) e.getKey().value() * e.getValue()).sum(); }
}

// DispenseResult.java
import java.util.Map;

public final class DispenseResult {
    public final Product product; public final Map<Denomination, Integer> change;
    public DispenseResult(Product product, Map<Denomination, Integer> change) { this.product = product; this.change = change; }
    @Override public String toString() { return "Dispensed " + product + ", change " + change; }
}

5.2 Change making (Strategy)

// ChangeMaker.java
import java.util.Map;
import java.util.Optional;

/** Strategy: how to build change from available coins. Pure function on a snapshot. */
public interface ChangeMaker {
    Optional<Map<Denomination, Integer>> make(int amount, Map<Denomination, Integer> available);
}

// GreedyChangeMaker.java
import java.util.*;

/**
 * Greedy largest-first. Optimal for canonical coin systems (1,2,5,10,20,50,100) when stock is unlimited;
 * with limited stock it can miss a valid combination - swap in a DP implementation of ChangeMaker if required.
 */
public final class GreedyChangeMaker implements ChangeMaker {
    @Override
    public Optional<Map<Denomination, Integer>> make(int amount, Map<Denomination, Integer> available) {
        Map<Denomination, Integer> change = new EnumMap<>(Denomination.class);
        List<Denomination> desc = new ArrayList<>(List.of(Denomination.values()));
        Collections.reverse(desc);
        int left = amount;
        for (Denomination d : desc) {
            int n = Math.min(left / d.value(), available.getOrDefault(d, 0));
            if (n > 0) { change.put(d, n); left -= n * d.value(); }
        }
        return left == 0 ? Optional.of(change) : Optional.empty();
    }
}

5.3 States

// VendingState.java
import java.util.Map;

public interface VendingState {
    String name();
    default void insertMoney(VendingMachine m, Denomination d)   { reject("insert money"); }
    default DispenseResult selectProduct(VendingMachine m, String code) { reject("select a product"); return null; }
    default Map<Denomination, Integer> cancel(VendingMachine m)  { reject("cancel"); return null; }
    private void reject(String op) { throw new VendingException("Cannot " + op + " while " + name()); }
}

// IdleState.java
public final class IdleState implements VendingState {
    public static final IdleState INSTANCE = new IdleState();
    private IdleState() {}
    @Override public String name() { return "IDLE"; }
    @Override public void insertMoney(VendingMachine m, Denomination d) {
        m.acceptMoney(d);
        m.setState(HasMoneyState.INSTANCE);
    }
    @Override public DispenseResult selectProduct(VendingMachine m, String code) {
        throw new VendingException("Please insert money first");
    }
}

// HasMoneyState.java
import java.util.Map;
import java.util.Optional;

public final class HasMoneyState implements VendingState {
    public static final HasMoneyState INSTANCE = new HasMoneyState();
    private HasMoneyState() {}
    @Override public String name() { return "HAS_MONEY"; }

    @Override public void insertMoney(VendingMachine m, Denomination d) { m.acceptMoney(d); }

    @Override public DispenseResult selectProduct(VendingMachine m, String code) {
        Slot slot = m.inventory().slot(code);
        if (slot.isSoldOut()) throw new VendingException(slot.product().name() + " is sold out");
        int price = slot.product().price();
        if (m.balance() < price)
            throw new VendingException("Insufficient amount: need Rs " + (price - m.balance()) + " more");

        // dry run: can we make change using machine stock + the coins just inserted?
        Optional<Map<Denomination, Integer>> change = m.changeMaker().make(m.balance() - price, m.cashPlusInserted());
        if (change.isEmpty())
            throw new VendingException("Exact change only: cannot return Rs " + (m.balance() - price)
                    + ". Add exact amount or cancel");

        m.setState(DispensingState.INSTANCE);
        return DispensingState.INSTANCE.dispense(m, slot, change.get());
    }

    @Override public Map<Denomination, Integer> cancel(VendingMachine m) {
        Map<Denomination, Integer> refund = m.takeInsertedMoney();
        m.setState(IdleState.INSTANCE);
        return refund;
    }
}

// DispensingState.java
import java.util.Map;

/** Transient state: while the motor turns, every external input is rejected (default methods). */
public final class DispensingState implements VendingState {
    public static final DispensingState INSTANCE = new DispensingState();
    private DispensingState() {}
    @Override public String name() { return "DISPENSING"; }

    DispenseResult dispense(VendingMachine m, Slot slot, Map<Denomination, Integer> change) {
        try {
            slot.take();                       // physically drop the item
            m.commitSale(change);              // inserted coins -> cash box, change coins out
            return new DispenseResult(slot.product(), change);
        } finally {
            m.setState(m.inventory().allSoldOut() ? OutOfServiceState.INSTANCE : IdleState.INSTANCE);
        }
    }
}

// OutOfServiceState.java
import java.util.Map;

public final class OutOfServiceState implements VendingState {
    public static final OutOfServiceState INSTANCE = new OutOfServiceState();
    private OutOfServiceState() {}
    @Override public String name() { return "OUT_OF_SERVICE"; }
    @Override public Map<Denomination, Integer> cancel(VendingMachine m) { return m.takeInsertedMoney(); }
}

5.4 Context

// VendingMachine.java
import java.util.*;

/**
 * State-pattern context. One customer at a time at the physical keypad => all public methods synchronized.
 * (Admin operations share the same monitor so a restock cannot interleave with a sale.)
 */
public final class VendingMachine {
    private final Inventory inventory;
    private final CashBox cashBox = new CashBox();
    private final ChangeMaker changeMaker;
    private final Map<Denomination, Integer> inserted = new EnumMap<>(Denomination.class);
    private VendingState state = IdleState.INSTANCE;

    public VendingMachine(Inventory inventory, ChangeMaker changeMaker) {
        this.inventory = inventory; this.changeMaker = changeMaker;
    }

    // ---- customer API ----
    public synchronized void insertMoney(Denomination d) { state.insertMoney(this, d); }
    public synchronized DispenseResult selectProduct(String code) { return state.selectProduct(this, code); }
    public synchronized Map<Denomination, Integer> cancel() { return state.cancel(this); }
    public synchronized String stateName() { return state.name(); }
    public synchronized int currentBalance() { return balance(); }

    // ---- admin API ----
    public synchronized void restock(String code, int qty) {
        inventory.restock(code, qty);
        if (state == OutOfServiceState.INSTANCE) state = IdleState.INSTANCE;
    }
    public synchronized void loadChange(Denomination d, int n) { cashBox.add(d, n); }
    public synchronized long cashInMachine() { return cashBox.total(); }
    public synchronized String inventorySummary() { return inventory.summary(); }

    // ---- hooks for states ----
    void setState(VendingState s) { state = s; }
    Inventory inventory() { return inventory; }
    ChangeMaker changeMaker() { return changeMaker; }
    void acceptMoney(Denomination d) { inserted.merge(d, 1, Integer::sum); }
    int balance() { return inserted.entrySet().stream().mapToInt(e -> e.getKey().value() * e.getValue()).sum(); }
    Map<Denomination, Integer> cashPlusInserted() {
        Map<Denomination, Integer> all = cashBox.snapshot();
        inserted.forEach((d, n) -> all.merge(d, n, Integer::sum));
        return all;
    }
    Map<Denomination, Integer> takeInsertedMoney() {
        Map<Denomination, Integer> refund = new EnumMap<>(Denomination.class);
        refund.putAll(inserted);
        inserted.clear();
        return refund;
    }
    void commitSale(Map<Denomination, Integer> change) {
        cashBox.addAll(inserted);
        inserted.clear();
        cashBox.remove(change);
    }
}

5.5 Demo driver

// Main.java
public class Main {
    static void attempt(String label, Runnable r) {
        try { r.run(); } catch (VendingException e) { System.out.println("  [" + label + "] " + e.getMessage()); }
    }

    public static void main(String[] args) {
        Inventory inv = new Inventory();
        inv.addSlot(new Slot("A1", new Product("Chips", 20), 2));
        inv.addSlot(new Slot("A2", new Product("Soda", 35), 1));
        inv.addSlot(new Slot("B1", new Product("Choco", 50), 5));
        VendingMachine vm = new VendingMachine(inv, new GreedyChangeMaker());
        vm.loadChange(Denomination.TEN, 5); vm.loadChange(Denomination.FIVE, 5);
        vm.loadChange(Denomination.TWO, 5); vm.loadChange(Denomination.ONE, 5);
        System.out.println("Stock: " + vm.inventorySummary() + " | cash Rs " + vm.cashInMachine());

        System.out.println("== 1. select before paying ==");
        attempt("select", () -> vm.selectProduct("A1"));

        System.out.println("== 2. pay 50, buy Chips(20): change 30 ==");
        vm.insertMoney(Denomination.FIFTY);
        System.out.println("  state=" + vm.stateName() + " balance=" + vm.currentBalance());
        System.out.println("  " + vm.selectProduct("A1") + "  state=" + vm.stateName());

        System.out.println("== 3. insufficient, top up, buy Soda(35) ==");
        vm.insertMoney(Denomination.TWENTY);
        attempt("select", () -> vm.selectProduct("A2"));
        vm.insertMoney(Denomination.TWENTY);
        System.out.println("  " + vm.selectProduct("A2"));

        System.out.println("== 4. sold out + cancel refunds ==");
        vm.insertMoney(Denomination.TEN); vm.insertMoney(Denomination.TEN);
        attempt("select", () -> vm.selectProduct("A2"));
        attempt("bad code", () -> vm.selectProduct("Z9"));
        System.out.println("  refund " + vm.cancel() + " state=" + vm.stateName());
        attempt("cancel when idle", vm::cancel);

        System.out.println("== 5. exact-change-only machine (no coins loaded) ==");
        Inventory inv2 = new Inventory();
        inv2.addSlot(new Slot("A1", new Product("Chips", 20), 1));
        VendingMachine poor = new VendingMachine(inv2, new GreedyChangeMaker());
        poor.insertMoney(Denomination.FIFTY);
        attempt("select", () -> poor.selectProduct("A1"));
        System.out.println("  refund " + poor.cancel());
        poor.insertMoney(Denomination.TWENTY);
        System.out.println("  " + poor.selectProduct("A1") + "  state=" + poor.stateName());
        attempt("insert", () -> poor.insertMoney(Denomination.TEN));
        poor.restock("A1", 3);
        System.out.println("  after restock state=" + poor.stateName() + " | " + poor.inventorySummary());

        System.out.println("Final main machine: " + vm.inventorySummary() + " | cash Rs " + vm.cashInMachine());
    }
}

Real output (from java Main)

Stock: A1=Chipsx2 A2=Sodax1 B1=Chocox5 | cash Rs 90
== 1. select before paying ==
  [select] Please insert money first
== 2. pay 50, buy Chips(20): change 30 ==
  state=HAS_MONEY balance=50
  Dispensed Chips(Rs 20), change {TEN=3}  state=IDLE
== 3. insufficient, top up, buy Soda(35) ==
  [select] Insufficient amount: need Rs 15 more
  Dispensed Soda(Rs 35), change {FIVE=1}
== 4. sold out + cancel refunds ==
  [select] Soda is sold out
  [bad code] Invalid selection Z9
  refund {TEN=2} state=IDLE
  [cancel when idle] Cannot cancel while IDLE
== 5. exact-change-only machine (no coins loaded) ==
  [select] Exact change only: cannot return Rs 30. Add exact amount or cancel
  refund {FIFTY=1}
  Dispensed Chips(Rs 20), change {}  state=OUT_OF_SERVICE
  [insert] Cannot insert money while OUT_OF_SERVICE
  after restock state=IDLE | A1=Chipsx3
Final main machine: A1=Chipsx1 A2=Sodax0 B1=Chocox5 | cash Rs 145

Cash check: the machine started with Rs 90 of coins. Sale 1: +50 inserted -30 change = +20 -> 110. Sale 2: +40 -5 = +35 -> 145. Matches Final ... cash Rs 145.

6. Walkthrough of key flows

Buy Chips(20) with a Rs 50 note
User        VendingMachine       HasMoneyState         ChangeMaker      Slot/CashBox
 |--insert 50-->| Idle.insertMoney: acceptMoney(50); state=HAS_MONEY
 |--select A1-->|---selectProduct--->|
 |              |                    |-slot sold out? price<=balance? ok
 |              |                    |--make(30, cash+inserted)--->| greedy => {TEN:3}
 |              |                    |   (empty => throw "Exact change only", nothing changed)
 |              |                    |-state=DISPENSING
 |              |                    |-slot.take(); commitSale(change): inserted->cashBox, change out
 |              |                    |-finally: state = IDLE (or OUT_OF_SERVICE if all sold out)
 |<-Chips + {TEN:3}

Order matters: validate and dry-run everything first, then mutate (take item, move coins). If anything throws before the mutation, the customer's money is still held and can be cancelled/refunded. finally guarantees the machine never gets stuck in DISPENSING.

7. Extensibility

  • New state (MAINTENANCE, CARD_PAYMENT_PENDING): new class implementing VendingState; only the transitions into/out of it change.
  • Cards/UPI: introduce PaymentMethod strategy: CashPayment (current), UpiPayment (collect request -> callback -> state AWAITING_PAYMENT); change is not needed for digital payments. HasMoneyState delegates "is paid?" to the strategy.
  • Pricing rules (discounts, happy hour): PricingStrategy replacing product.price() in HasMoneyState.
  • Different change algorithm: implement ChangeMaker (DP with bounded coins, or "minimise coin depletion").
  • Multiple items per session: keep a cart in the context; selectProduct adds to the cart; new CheckoutState.
  • Alerts/telemetry: Observer on inventory/cash changes.

8. Concurrency and edge cases

  • Locking: all public methods are synchronized on the machine. A physical kiosk has one keypad; contention is negligible and one monitor protects the state field, inserted coins, cash box and inventory together (admin restock cannot interleave with a sale). Finer-grained locks would add risk for no benefit. For a remote-controlled/IoT variant use a single-threaded executor (actor) per machine instead of a lock.
  • Atomic sale: dry-run -> mutate; mutation steps do not throw. finally restores state.
  • Exact-change-only: calculation includes coins just inserted by the customer; if still impossible, nothing is taken.
  • Greedy with limited coins can miss valid combos (e.g. need 6 with {5:1, 2:3}: greedy picks 5 then needs 1 -> fail, DP finds 2+2+2). Say it, swap the strategy.
  • Cancel while IDLE rejected; insert in DISPENSING/OUT_OF_SERVICE rejected (note: out-of-service could instead eject the coin).
  • Edge cases: negative/zero quantity restock, invalid slot code, balance exactly equal to price, overpayment beyond capacity of coins, power loss mid-sale (journal inserted coins to non-volatile memory, refund on boot), counterfeit coin detection (hardware).

9. Follow-up questions and model answers

  1. Why State instead of an enum + switch? OCP and cohesion: behaviour per state is localised; invalid operations are structurally rejected; adding a state does not modify others.
  2. How to make it support UPI? PaymentMethod interface with collect(amount) returning future status; HasMoneyState becomes AwaitingPaymentState that transitions on the callback; handle timeout -> cancel -> IDLE. The same idempotency/callback concerns as a payment gateway (file 06).
  3. Persist/recover? Persist a small journal: session id, inserted coins, state, selected slot; after reboot, recover to refund or complete. Inventory and cash counts in local DB (SQLite) updated in the same transaction as the sale record.
  4. Fleet of machines / distributed? Each machine is autonomous (offline-capable). Central service gets sale events (at-least-once, idempotent by machineId+saleSeq), pushes pricing/planogram updates, and tracks restock needs. Machine IDs are the shard key.
  5. How to handle price change during a session? Capture price when the product is selected / session starts, or reject changes while not IDLE.
  6. Min coin change optimally with limited coins? Bounded knapsack DP O(amount x denominations x count) or BFS; fine for small amounts.
  7. Thread-safety if multiple sessions (app-driven)? Then it is no longer one kiosk: add a Session object per customer; shared inventory needs reserve-on-select (decrement qty with CAS, release on timeout).
  8. Testing? State classes are stateless: unit test by constructing a machine with fixtures; inject a ChangeMaker fake.

10. Common mistakes, red flags, rubric

Red flags

  • Booleans like isMoneyInserted, isDispensing instead of State.
  • States holding a reference to the machine as a field plus public setters everywhere (tight cycles) with no clear transitions.
  • Taking the money before checking change/stock (no refund path).
  • Machine stuck in DISPENSING after an exception (no finally).
  • Hard-coded if (balance > 50) return 50... change logic.
  • God VendingMachine that contains inventory maps, coin maps and all rules.
  • double for rupees.

Mini rubric (20 pts)

AreaPoints
Requirements, scope, assumptions3
States and transitions drawn and coded correctly6
Change-making + exact-change handling4
Atomic sale (validate -> mutate), refund path3
Runnable demo with edge cases2
Extensibility/follow-ups (UPI, persistence)2