Vending Machine

Design a coin-operated vending machine whose behaviour depends on what has happened so far. It is the classic problem for the State pattern.

Design a vending machine for an office. It sells snacks and drinks from numbered slots. Users insert coins, choose a product, and get the product and their change. They can cancel before choosing.

Questions to ask first

  • Which money does it take? Assume Indian coins of 1, 2, 5, 10 and 20 rupees. Notes and UPI are extensions.
  • Can one purchase take several coins? Yes. The balance builds up until the user chooses.
  • What if exact change is not possible? Refuse the sale, keep the user's money as balance, and ask them to cancel or pick another product.
  • One product per purchase? Yes. After dispensing, the machine returns change and goes back to waiting.
  • Who restocks? An operator with a key. Assume a `restock(code, count)` method with no login.

Requirements

  • Accept coins and keep a running balance.
  • Let the user select a product by slot code. Dispense it if the balance covers the price and it is in stock.
  • Return correct change from the coins in the machine. Refuse the sale if change is not possible.
  • Cancel at any time before dispensing and return the inserted coins.
  • Reject actions that make no sense in the current state, such as selecting before paying.
  • Show sold out when every slot is empty. Restocking brings the machine back.

Out of scope

  • Notes, cards and UPI payments.
  • Operator login and sales reports.
  • Hardware details of motors and coin sensors.

Entities

  • VendingMachine: state, balance, inserted coins; insertCoin(coin), selectProduct(code), cancel(), restock(code, count)
  • MachineState: the same actions, answered differently in each state
  • IdleState, HasMoneyState, DispensingState, SoldOutState
  • Inventory: slots; slot(code), isEmpty(), restock(code, count)
  • Slot: code, product, count; takeOne()
  • Product: name, price
  • CoinBox: coin counts; acceptPayment(paid, change)
  • Coin: ONE, TWO, FIVE, TEN, TWENTY, each with a value

Classes in the model design

  • VendingMachine (class)
  • MachineState (interface)
  • IdleState (class)
  • HasMoneyState (class)
  • DispensingState (class)
  • SoldOutState (class)
  • Inventory (class)
  • Slot (class)
  • Product (class)
  • CoinBox (class)
  • Coin (enum)

The main use case, step by step

  1. The machine starts in IdleState. A user inserts a 10 rupee coin. `VendingMachine.insertCoin` makes no checks itself: it calls `state.insertCoin(this, coin)`.
  2. IdleState adds the coin to the balance and calls `machine.setState(hasMoney)`. A second 10 rupee coin reaches HasMoneyState, which adds it too. The balance is 20.
  3. The user selects slot B2, a 15 rupee packet of chips. HasMoneyState checks that the slot is not empty and that the balance covers the price.
  4. HasMoneyState asks CoinBox for 5 rupees of change. CoinBox adds the paid coins to its counts, then picks coins from the largest value down. If it cannot make 5, it undoes everything and the sale is refused.
  5. With change ready, the state becomes DispensingState. The machine takes one item from the slot, drops it and returns the change.
  6. The machine then moves to SoldOutState if every slot is empty, or back to IdleState. Pressing select in IdleState now gives the error "Insert money first".

Patterns used

  • State: MachineState with IdleState, HasMoneyState, DispensingState and SoldOutState. VendingMachine holds the current one.. The same button does different things in different states. Each state class answers every action, so no switch on state is repeated in every method, and a new state is a new class.
  • Encapsulation of money and stock: CoinBox owns the coin counts; Inventory owns the slots.. The machine never edits counts directly. CoinBox checks that change is possible before it changes anything, so the counts never go wrong.

Key code

The state interface and two states

public interface MachineState {
    void insertCoin(VendingMachine m, Coin coin);
    void selectProduct(VendingMachine m, String code);
    void cancel(VendingMachine m);
}

public final class IdleState implements MachineState {
    @Override public void insertCoin(VendingMachine m, Coin coin) { m.addCoin(coin); m.setState(m.hasMoney); }
    @Override public void selectProduct(VendingMachine m, String code) { throw new IllegalStateException("Insert money first"); }
    @Override public void cancel(VendingMachine m) { }   // nothing to return
}

public final class HasMoneyState implements MachineState {
    @Override
    public void insertCoin(VendingMachine m, Coin coin) { m.addCoin(coin); }

    @Override
    public void selectProduct(VendingMachine m, String code) {
        Slot slot = m.inventory().slot(code);
        if (slot.isEmpty()) throw new IllegalStateException("Sold out: " + code);
        int price = slot.product().price();
        if (m.balance() < price) {
            throw new IllegalStateException("Insert " + (price - m.balance()) + " more rupees");
        }
        // Check change BEFORE anything moves. On failure the balance stays and the user can cancel.
        List<Coin> change = m.coinBox().acceptPayment(m.inserted(), m.balance() - price)
            .orElseThrow(() -> new IllegalStateException("No change for this item. Pick another or cancel."));
        m.setState(m.dispensing);
        m.dispense(slot, change);
    }

    @Override
    public void cancel(VendingMachine m) {
        m.refund();
        m.setState(m.idle);
    }
}

VendingMachine: the context that passes buttons to its state

public final class VendingMachine {
    final MachineState idle = new IdleState();
    final MachineState hasMoney = new HasMoneyState();
    final MachineState dispensing = new DispensingState();
    final MachineState soldOut = new SoldOutState();

    private final Inventory inventory;
    private final CoinBox coinBox;
    private final List<Coin> inserted = new ArrayList<>();
    private MachineState state;
    private int balance;

    public VendingMachine(Inventory inventory, CoinBox coinBox) {
        this.inventory = inventory;
        this.coinBox = coinBox;
        this.state = inventory.isEmpty() ? soldOut : idle;
    }

    // Buttons. synchronized: the operator may restock while a user is buying.
    public synchronized void insertCoin(Coin c) { state.insertCoin(this, c); }
    public synchronized void selectProduct(String code) { state.selectProduct(this, code); }
    public synchronized void cancel() { state.cancel(this); }

    public synchronized void restock(String code, int count) {
        inventory.restock(code, count);
        if (state == soldOut) state = idle;
    }

    // Used by the state classes in the same package.
    void setState(MachineState next) { this.state = next; }
    void addCoin(Coin c) { inserted.add(c); balance += c.value(); }
    int balance() { return balance; }
    List<Coin> inserted() { return List.copyOf(inserted); }
    Inventory inventory() { return inventory; }
    CoinBox coinBox() { return coinBox; }

    void refund() { eject(inserted); clearPayment(); }

    void dispense(Slot slot, List<Coin> change) {
        drop(slot.takeOne());
        eject(change);
        clearPayment();
        setState(inventory.isEmpty() ? soldOut : idle);
    }

    private void clearPayment() { inserted.clear(); balance = 0; }
    private void drop(Product p) { System.out.println("Dropped " + p.name()); }
    private void eject(List<Coin> coins) { System.out.println("Returned " + coins); }
}

Coins and change that rolls back on failure

public enum Coin {
    ONE(1), TWO(2), FIVE(5), TEN(10), TWENTY(20);

    private final int value;
    Coin(int value) { this.value = value; }
    public int value() { return value; }
}

public final class CoinBox {
    private final EnumMap<Coin, Integer> counts = new EnumMap<>(Coin.class);

    /** Adds the paid coins, then takes change out. If change is impossible, nothing changes. */
    public Optional<List<Coin>> acceptPayment(List<Coin> paid, int change) {
        paid.forEach(c -> counts.merge(c, 1, Integer::sum));
        List<Coin> out = new ArrayList<>();
        int left = change;
        Coin[] largestFirst = Coin.values();
        for (int i = largestFirst.length - 1; i >= 0; i--) {
            Coin c = largestFirst[i];
            while (left >= c.value() && counts.getOrDefault(c, 0) > 0) {
                counts.merge(c, -1, Integer::sum);
                out.add(c);
                left -= c.value();
            }
        }
        if (left == 0) return Optional.of(out);
        out.forEach(c -> counts.merge(c, 1, Integer::sum));    // undo the change taken
        paid.forEach(c -> counts.merge(c, -1, Integer::sum));  // undo the payment
        return Optional.empty();
    }
}

Deep dives

Modelling the machine's behaviour

Weak: Booleans: hasMoney, isDispensing, isSoldOut. Every method checks them in a different order. Nothing stops two of them being true at once, and bugs hide in the combinations.

Good: One enum State { IDLE, HAS_MONEY, DISPENSING, SOLD_OUT } and a switch in every action method. The machine is in exactly one state, which fixes the worst bug. But adding a state means editing every switch.

Great: The State pattern. A MachineState interface has one class per state, and the machine passes each button press to its current state. The state decides what the action does and which state comes next. A new state, such as MAINTENANCE, is one new class.

Trade-off: Four classes for four states is more code than one switch. For two or three states with simple rules, an enum with a switch is fine. Choose the pattern when states and actions both grow.

Giving change

Weak: Assume the machine has unlimited coins of every value, and return balance - price as a number. It works until the machine runs out of 1 rupee coins.

Good: Track the count of each coin in CoinBox. Pick coins greedily, from the largest value down. For Indian coins (1, 2, 5, 10, 20), greedy gives the fewest coins when every value is in stock.

Great: Check change before the sale, and roll back if it fails. acceptPayment adds the paid coins, tries to build change, and undoes everything if it cannot. Greedy can also fail when some coins run out. For 6 rupees with only 5s and 2s, greedy takes 5 and gets stuck, but 2 + 2 + 2 works. A small dynamic-programming search (try counts and remember the best) finds those answers.

Trade-off: Greedy is fast and fine for an interview. Mention the stock problem and the dynamic-programming fix to show depth. Refusing a sale is always safer than losing money.

What if the item gets stuck?

Weak: Keep the money, reduce the stock, then run the motor. If the item gets stuck, the user has paid and gets nothing, and the stock count is wrong.

Good: Run the motor first and check the drop sensor. Only then reduce the stock and keep the money. If the sensor sees nothing, refund the balance and mark the slot as faulty.

Great: Treat a sale as a small transaction with steps that can each be undone: reserve the item, accept payment, dispense, confirm. DispensingState waits for the sensor and moves to Idle on success or to a refund path on failure. Log every step so an operator can settle complaints.

Trade-off: This means more states and more code, but no lost money. In a 90-minute round, describe it and code the normal path.

Now add one more feature

  • Now accept UPI. Add a `PaymentMethod` interface with `CoinPayment` and `UpiPayment`. HasMoneyState asks the payment method whether the amount is covered. UPI needs no change, so the change step is skipped for it.
  • Now add an operator maintenance mode. Add a `MaintenanceState` that refuses user actions and allows restock and coin collection. Only the new class and one entry method change.
  • Now refund automatically if the user does nothing for 60 seconds. Add a `timeout()` action to MachineState. HasMoneyState refunds; the other states ignore it. A timer calls it.
  • Now show prices and stock on a screen. Add a read-only method on Inventory that returns code, product and count for each slot. The screen reads it and never changes the state.

What each level is expected to show

SDE-1: Clear classes for machine, inventory, slot, product and coins. A state enum or the State pattern with the main transitions. Correct balance and change on the normal path, and a clear error for selecting before paying.

SDE-2: The State pattern with a reason for choosing it, a state diagram with guards, and change that is checked before the sale and rolled back on failure. Has a plan for a stuck item, and explains when greedy change works and when it fails.

Common mistakes

  • Putting the whole flow in one `selectProduct` method full of `hasMoney && !dispensing` checks.
  • Reducing stock or keeping the money before the item has actually dropped.
  • Forgetting that change can be impossible, so the machine takes money it cannot settle.
  • Letting a select in IdleState do nothing silently, instead of giving a clear error.
  • Storing the count on Product. Stock belongs to a slot, because the same product can sit in two slots.

Lessons behind this answer