Low Level Design: Vending Machine (State Design Pattern)

Every list of design pattern examples uses the vending machine for the State pattern, and most of them stop at four classes that print "Please insert coin". That is enough to recognise the pattern but not enough to pass an LLD round, where the interviewer will ask what happens when the machine cannot return change, what a coin inserted mid-dispense does, and how the admin restocks without corrupting a customer's transaction.

This guide does the full job: the bad version first so you can see why State helps, then a transition table, escrow, a change-making algorithm that is actually correct, and complete Java. For how this fits into LLD preparation overall, see the LLD interview guide.

Vending Machine Requirements

Functional

1. Accept coins and notes (₹1, ₹2, ₹5, ₹10, ₹20 coins/notes; ₹50 and ₹100 notes accepted but never given as change).
2. User selects a product by code (A1, A2, B1...). If paid enough and in stock, dispense the product and the change.
3. User can cancel at any time before dispensing and get their exact coins back.
4. Reject sales that are sold out, underpaid, or for which correct change cannot be returned.
5. An operator can put the machine in service mode to restock products and load coins.

Clarifying questions worth asking

• Pay first or select first? Most Indian office machines are pay-first; card/UPI machines are select-first. We design pay-first and show select-first as an extension.
• One item per transaction or several? One; multiple is an extension that keeps the HasMoney state.
• Digital payments? UPI QR and cards are common now. Model payment as a pluggable source later.
• What if change is impossible? Refuse the sale, never short-change. Confirm this; it drives the escrow design.

Why the State Pattern? Start with the Version That Breaks

Here is the design most people write first:

void insertCoin(int value) {
    if (outOfService) throw new IllegalStateException("Out of service");
    if (dispensing) throw new IllegalStateException("Please wait");
    balance += value;
    hasMoney = true;
}

void select(String code) {
    if (outOfService) throw new IllegalStateException("Out of service");
    if (dispensing) throw new IllegalStateException("Please wait");
    if (!hasMoney) throw new IllegalStateException("Insert money first");
    // ... price checks, stock checks, change ...
    dispensing = true;
    // ...
    dispensing = false;
    hasMoney = false;
}

Three booleans mean eight combinations, most of them meaningless (outOfService && dispensing && hasMoney?), and every method re-checks all of them. Add a "ProductSelected" step for UPI payments and every method grows another branch. The bugs are in the combinations nobody thought about.

The State pattern turns each meaningful combination into one class. The machine (the context) holds a reference to its current state and delegates every action to it. Each state implements only the actions that make sense for it; everything else falls through to a default "not allowed now". Illegal combinations become unrepresentable. The top 10 design patterns guide compares State with Strategy, which looks structurally identical; the difference is that states replace each other based on what happens, while a strategy is chosen from outside.

State Transition Table

Draw this before writing a line of code. It is the specification, and each cell becomes a test case.

Vending Machine Class Design

Two design details worth calling out:

• States are stateless singletons. All data (escrow, stock, coins) lives on the machine. States are pure behaviour, so one instance of each is enough.
• The interface has default methods that reject. Each state overrides only what it allows. Adding a new action (say tapCard) means one default plus overrides only where it is legal.

Escrow: Why Inserted Money Is Not in the Cash Box Yet

A real coin mechanism holds inserted coins in an escrow area until the sale is decided, then either drops them into the cash box or returns them. Model it the same way. The benefits are concrete:

• Exact refunds. Cancel returns the very coins inserted: a ₹100 note comes back as a ₹100 note, not as a pile of ₹10 coins the machine might not have.
• Atomic sales. The sale commits in one step: escrow moves to the cash box, change leaves the cash box, stock decrements. If any check fails before that step, nothing has changed.
• Escrow counts toward change planning. The escrowed coins will be in the cash box the instant the sale commits, so the planner may use them. If a customer pays ₹30 with a ₹20 coin and a ₹10 coin for a ₹20 item, the machine can hand back that same ₹10 coin even if its own ₹10 tube is empty.

Change-Making: When Greedy Fails

The obvious algorithm is greedy: give the largest coin that fits, repeat. For a standard ("canonical") coin system with unlimited coins, greedy gives the fewest coins. A vending machine does not have unlimited coins.

The counterexample

Change due: ₹6. Coins available: one ₹5, three ₹2, zero ₹1.

• Greedy: take ₹5 (₹1 left), no ₹1 coin, no ₹2 fits. Fails, so the machine refuses a sale it could have completed.
• Correct: ₹2 + ₹2 + ₹2.

Bounded coin change with dynamic programming

Process denominations one at a time. Let dp[i][a] be the fewest coins to make amount a using only the first i denominations, with at most count[i] coins of denomination i:

dp[i][a] = min over k in 0..count[i], k·value[i] ≤ a, of dp[i−1][a − k·value[i]] + k

Store the chosen k in take[i][a] to reconstruct the plan. Time is O(D × A × C) for D denominations, change amount A and maximum count C. For a vending machine (5 denominations, change under ₹100, at most a few hundred coins) that is well under a million steps. If no finite dp[D][A] exists, change is impossible and the sale is refused.

This is the bounded variant of LeetCode 322; the unbounded version and its DP intuition are explained in Coin Change explained, and the general family in knapsack DP patterns.

Full Java Code for the Vending Machine

Java 17+, single file, run with java VendingMachineDemo.java.

import java.util.*;

public class VendingMachineDemo {

    enum Denomination {
        ONE(1, true), TWO(2, true), FIVE(5, true), TEN(10, true), TWENTY(20, true),
        FIFTY(50, false), HUNDRED(100, false);          // notes accepted, never given as change

        final int value;
        final boolean dispensable;
        Denomination(int value, boolean dispensable) {
            this.value = value;
            this.dispensable = dispensable;
        }
    }

    record Product(String code, String name, int price) { }

    record Sale(Product product, Map<Denomination, Integer> change) {
        @Override public String toString() {
            return "Dispensed " + product.name() + ", change Rs " + total(change) + " " + change;
        }
    }

    static final class VendingException extends RuntimeException {
        VendingException(String message) { super(message); }
    }

    static int total(Map<Denomination, Integer> coins) {
        return coins.entrySet().stream().mapToInt(e -> e.getKey().value * e.getValue()).sum();
    }

    // ===================== Inventory =====================
    static final class Inventory {
        private final Map<String, Product> products = new LinkedHashMap<>();
        private final Map<String, Integer> stock = new HashMap<>();

        void add(Product p, int qty) {
            products.put(p.code(), p);
            stock.merge(p.code(), qty, Integer::sum);
        }

        Product find(String code) {
            Product p = products.get(code);
            if (p == null) throw new VendingException("Unknown product code " + code);
            return p;
        }

        boolean inStock(String code) { return stock.getOrDefault(code, 0) > 0; }

        void takeOne(String code) { stock.merge(code, -1, Integer::sum); }
    }

    // ===================== Cash box + change making =====================
    static final class CashBox {
        private final EnumMap<Denomination, Integer> counts = new EnumMap<>(Denomination.class);

        CashBox() { for (Denomination d : Denomination.values()) counts.put(d, 0); }

        void deposit(Map<Denomination, Integer> coins) { coins.forEach((d, n) -> counts.merge(d, n, Integer::sum)); }

        void withdraw(Map<Denomination, Integer> coins) { coins.forEach((d, n) -> counts.merge(d, -n, Integer::sum)); }

        EnumMap<Denomination, Integer> snapshot() { return new EnumMap<>(counts); }

        /** Plans change from cash box + escrow (escrow will be deposited when the sale commits). */
        Optional<Map<Denomination, Integer>> planChange(int amount, Map<Denomination, Integer> escrow) {
            EnumMap<Denomination, Integer> available = snapshot();
            escrow.forEach((d, n) -> available.merge(d, n, Integer::sum));
            return fewestCoins(amount, available);
        }
    }

    /** Bounded coin change: fewest coins using at most available[d] of each dispensable denomination. */
    static Optional<Map<Denomination, Integer>> fewestCoins(int amount, Map<Denomination, Integer> available) {
        List<Denomination> denoms = Arrays.stream(Denomination.values()).filter(d -> d.dispensable).toList();
        int n = denoms.size();
        final int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n + 1][amount + 1];
        int[][] take = new int[n + 1][amount + 1];
        Arrays.fill(dp[0], INF);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            Denomination d = denoms.get(i - 1);
            int max = available.getOrDefault(d, 0);
            for (int a = 0; a <= amount; a++) {
                dp[i][a] = INF;
                for (int k = 0; k <= max && k * d.value <= a; k++) {
                    int candidate = dp[i - 1][a - k * d.value] + k;
                    if (candidate < dp[i][a]) {
                        dp[i][a] = candidate;
                        take[i][a] = k;
                    }
                }
            }
        }
        if (dp[n][amount] >= INF) return Optional.empty();
        Map<Denomination, Integer> plan = new EnumMap<>(Denomination.class);
        for (int i = n, a = amount; i >= 1; i--) {
            Denomination d = denoms.get(i - 1);
            int k = take[i][a];
            if (k > 0) plan.put(d, k);
            a -= k * d.value;
        }
        return Optional.of(plan);
    }

    // ===================== State pattern =====================
    interface State {
        String name();
        default void insert(VendingMachine vm, Denomination d) {
            throw new VendingException("Cannot insert money: machine is " + name());
        }
        default Sale select(VendingMachine vm, String code) {
            throw new VendingException("Cannot select: machine is " + name());
        }
        default Map<Denomination, Integer> cancel(VendingMachine vm) {
            throw new VendingException("Nothing to cancel: machine is " + name());
        }
    }

    static final class IdleState implements State {
        static final IdleState INSTANCE = new IdleState();
        public String name() { return "IDLE"; }

        public void insert(VendingMachine vm, Denomination d) {
            vm.escrow.merge(d, 1, Integer::sum);
            vm.setState(HasMoneyState.INSTANCE);
        }

        public Sale select(VendingMachine vm, String code) {
            throw new VendingException("Insert money first (price Rs " + vm.inventory.find(code).price() + ")");
        }
    }

    static final class HasMoneyState implements State {
        static final HasMoneyState INSTANCE = new HasMoneyState();
        public String name() { return "HAS_MONEY"; }

        public void insert(VendingMachine vm, Denomination d) { vm.escrow.merge(d, 1, Integer::sum); }

        public Sale select(VendingMachine vm, String code) {
            Product p = vm.inventory.find(code);
            if (!vm.inventory.inStock(code)) throw new VendingException(p.name() + " is sold out");
            int balance = vm.balance();
            if (balance < p.price()) throw new VendingException("Insert Rs " + (p.price() - balance) + " more");
            Map<Denomination, Integer> change = vm.cashBox.planChange(balance - p.price(), vm.escrow)
                    .orElseThrow(() -> new VendingException("Cannot make change; please use exact amount"));
            vm.setState(DispensingState.INSTANCE);
            return DispensingState.INSTANCE.dispense(vm, p, change);
        }

        public Map<Denomination, Integer> cancel(VendingMachine vm) {
            Map<Denomination, Integer> refund = vm.takeEscrow();
            vm.setState(IdleState.INSTANCE);
            return refund;
        }
    }

    static final class DispensingState implements State {
        static final DispensingState INSTANCE = new DispensingState();
        public String name() { return "DISPENSING"; }

        /** Commit point: everything below happens together or not at all. */
        Sale dispense(VendingMachine vm, Product p, Map<Denomination, Integer> change) {
            vm.cashBox.deposit(vm.takeEscrow());
            vm.cashBox.withdraw(change);
            vm.inventory.takeOne(p.code());
            // hardware: motor turns the spiral, coin hopper releases change
            vm.setState(IdleState.INSTANCE);
            return new Sale(p, change);
        }
    }

    static final class OutOfServiceState implements State {
        static final OutOfServiceState INSTANCE = new OutOfServiceState();
        public String name() { return "OUT_OF_SERVICE"; }
    }

    // ===================== Context =====================
    static final class VendingMachine {
        final Inventory inventory = new Inventory();
        final CashBox cashBox = new CashBox();
        final EnumMap<Denomination, Integer> escrow = new EnumMap<>(Denomination.class);
        private State state = IdleState.INSTANCE;

        // customer actions: delegated to the current state
        synchronized void insert(Denomination d) { state.insert(this, d); }
        synchronized Sale select(String code) { return state.select(this, code); }
        synchronized Map<Denomination, Integer> cancel() { return state.cancel(this); }

        // operator actions
        synchronized void enterService() {
            if (state != IdleState.INSTANCE) throw new VendingException("Finish or cancel the current transaction first");
            state = OutOfServiceState.INSTANCE;
        }
        synchronized void exitService() {
            if (state == OutOfServiceState.INSTANCE) state = IdleState.INSTANCE;
        }
        synchronized void restock(Product p, int qty) { requireService(); inventory.add(p, qty); }
        synchronized void loadCoins(Map<Denomination, Integer> coins) { requireService(); cashBox.deposit(coins); }

        synchronized String stateName() { return state.name(); }

        // used by states
        void setState(State s) { state = s; }
        int balance() { return total(escrow); }
        Map<Denomination, Integer> takeEscrow() {
            Map<Denomination, Integer> taken = new EnumMap<>(escrow);
            escrow.clear();
            return taken;
        }

        private void requireService() {
            if (state != OutOfServiceState.INSTANCE) throw new VendingException("Enter service mode first");
        }
    }

    static void attempt(Runnable action) {
        try {
            action.run();
        } catch (VendingException e) {
            System.out.println("   ! " + e.getMessage());
        }
    }

    public static void main(String[] args) {
        VendingMachine vm = new VendingMachine();
        vm.enterService();
        vm.restock(new Product("A1", "Glucose Biscuits", 14), 2);
        vm.restock(new Product("A2", "Cold Coffee", 35), 1);
        vm.restock(new Product("B1", "Chocolate", 45), 0);
        vm.loadCoins(Map.of(Denomination.TWO, 3, Denomination.FIVE, 2, Denomination.TEN, 2));
        vm.exitService();

        vm.insert(Denomination.FIFTY);
        System.out.println("1) " + vm.select("A2"));          // change 15 = 10 + 5

        vm.insert(Denomination.TWENTY);
        System.out.println("2) " + vm.select("A1"));          // change 6: greedy fails, DP gives 2+2+2

        vm.insert(Denomination.TEN);
        attempt(() -> vm.select("B1"));                        // sold out, stays HAS_MONEY
        System.out.println("3) refund " + vm.cancel());

        vm.insert(Denomination.HUNDRED);
        attempt(() -> vm.select("A1"));                        // change 86 impossible
        System.out.println("4) refund " + vm.cancel() + ", state " + vm.stateName());

        System.out.println("Cash box: " + vm.cashBox.snapshot());
    }
}

Demo Walkthrough

1) Dispensed Cold Coffee, change Rs 15 {FIVE=1, TEN=1}
2) Dispensed Glucose Biscuits, change Rs 6 {TWO=3}
   ! Chocolate is sold out
3) refund {TEN=1}
   ! Cannot make change; please use exact amount
4) refund {HUNDRED=1}, state IDLE
Cash box: {ONE=0, TWO=0, FIVE=1, TEN=1, TWENTY=1, FIFTY=1, HUNDRED=0}

1. Cold coffee with a ₹50 note. IDLE → HAS_MONEY on insert. Change due ₹15; the cash box has three ₹2, two ₹5, two ₹10. The DP's fewest-coin answer is ₹10 + ₹5. The commit deposits the ₹50 and removes the change. Back to IDLE.
2. Biscuits (₹14) with a ₹20 coin. Change due ₹6. Now there is one ₹5, three ₹2, no ₹1. Greedy would take the ₹5 and fail; the DP returns three ₹2 coins. The sale goes through.
3. Chocolate, sold out. select throws but the state stays HAS_MONEY, so the customer can pick something else or cancel. Cancel returns the exact ₹10 from escrow.
4. Biscuits with a ₹100 note. Change due ₹86, but the dispensable coins total only ₹35 (₹20 + ₹10 + ₹5). The plan fails before anything is committed. The customer cancels and gets the ₹100 note back. The machine ends IDLE with consistent stock and cash.

Extensions Interviewers Ask

Select first, then pay (UPI or card)

Add a ProductSelectedState: IDLE → (select) → PRODUCT_SELECTED → (payment confirmed) → DISPENSING. Payments become a PaymentSource strategy: CashPayment, UpiQrPayment (show a dynamic QR for the exact price and wait for the callback), CardPayment. A timeout in PRODUCT_SELECTED returns to IDLE. Because states are classes, none of the existing states change except IDLE's select.

Dispense failure and refunds

Spirals jam. If the drop sensor does not detect the product within a few seconds, the DISPENSING state should roll back: return the escrow (it has not been committed yet if you move the commit after sensor confirmation) or, for digital payments, trigger a refund. That is a reason to make DISPENSING a real state with a timer instead of a pass-through.

Multiple items per transaction

Stay in HAS_MONEY after a sale while balance remains, and give change only on "done" or cancel. The change plan then runs once at the end.

Telemetry and low-stock alerts

Observer: the machine publishes SaleCompleted, StockLow, CoinsLow events; a telemetry client sends them to the operator's backend so a technician restocks before customers see "sold out". This is how connected machines in offices and metro stations are typically managed.

Coin validation chain

Before a coin reaches escrow, it passes checks: weight, diameter, metal signature, counterfeit note detection. Each validator can accept, reject or pass to the next, which is Chain of Responsibility, the same pattern the ATM LLD uses for dispensing notes.

Exact change only mode

When the coin hopper is low, the machine can switch the display to "exact change only" proactively. This can be a flag checked in HAS_MONEY, or a separate state if behaviour differs enough (for example, rejecting notes entirely).

How to Present the Vending Machine in an Interview

1. Requirements (3 min). Pay-first, single item, cash with change, cancel, service mode. Ask what happens when change is impossible.
2. Transition table (5 min). States × events grid. This alone puts you ahead of most candidates.
3. Classes (5 min). Context, State interface with rejecting defaults, four states, Inventory, CashBox.
4. Code (20 min). States first, then the commit in DISPENSING, then change planning.
5. Edge cases and extensions (10 min). Greedy counterexample, escrow refunds, select-first flow, jam handling.

What interviewers listen for

• You can explain State vs Strategy in one sentence.
• Invalid actions in each state are handled deliberately, not by accident.
• You plan, then commit; no partial updates on failure.
• You know greedy change-making fails with limited coins and can fix it.
• Money is integers, never double.

Common mistakes

• Boolean flags instead of states, or states that are just an enum with a big switch in every method (acceptable for tiny machines, but then say why you chose it).
• States that hold data (balance in HasMoneyState), which breaks when you share state instances.
• Refunding "balance" as arbitrary coins instead of returning the escrowed ones.
• No service mode, so restocking races with a live transaction.
• Letting select in a failed case silently move to IDLE and keep the money.

The State pattern shows up again in the ATM machine design (card and PIN states) and in the elevator system. For timed rounds where you must code all of this in 90 minutes, follow the plan in the machine coding round guide.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.