Design it yourself · Chapter 22

Vending machine

Design a vending machine in a machine-coding interview: the State pattern, inventory, correct change-making with a limited coin supply, refunds, full Java and Python code, and concurrency.

IntermediateInterview priority: High50 min
On this page
  1. The problem: a machine that remembers
  2. 1. Clarify the requirements
  3. 2. Find the entities
  4. 3. The class design
  5. 4. Change-making: why greedy is not enough
  6. 5. The code
  7. 6. Concurrency
  8. 7. Extensions the interviewer will ask for
  9. When not to over-design
  10. In the interview
  11. Quiz

The problem: a machine that remembers

"Design a vending machine" looks like a toy, and that is why candidates fail it. The behaviour of every button depends on what has already happened: pressing A1 does nothing until money is in, a coin dropped in while a snack is falling must come back, and "cancel" means something different before and after you've paid. The usual first attempt is a pile of flags:

class VendingMachine {
    boolean hasMoney, dispensing;
    double balance;                                   // dollars as a double

    void select(String code) {
        if (dispensing) return;
        if (!hasMoney) { show("Insert money"); return; }
        Slot s = slots.get(code);
        if (balance < s.price) { show("Insert more"); return; }
        dispensing = true;
        drop(s);
        giveChange(balance - s.price);                // assumes change is always possible
        balance = 0; hasMoney = false; dispensing = false;
    }
}

Four problems an interviewer will find: the flags allow impossible combinations (dispensing && !hasMoney); a double balance turns $0.10 + $0.20 into 0.30000000000000004; the machine promises change it may not be able to give; and it charges the customer even if the snack gets stuck. This page fixes all four.

A vending machine is a state machine

  1. A vending machine looks simple, but it’s a great design question because its behaviour depends on what has already happened. Pressing “A1” does nothing until you’ve paid. That makes it a state machine.

1. Clarify the requirements

Your turn: scope it

The interviewer says only "Design a vending machine." Write 5–6 questions you would ask, then the requirements you would agree on and two things you would leave out.

Compare with our answer

Questions worth asking: Which coins or notes are accepted? Cards? Can a customer buy several items in one session? What if the machine can't make change? What if an item gets stuck? Who restocks it, and can that happen while someone is buying? One machine, or a fleet reporting to a server?

A strong answer mentions: accepted coins and integer cents · selecting a slot code · change-making that can fail · cancel and refund · sold-out and stuck-item handling · a technician mode for restocking · explicit out-of-scope items (cards, networking).

The agreed list for this page:

FunctionalDetail
ProductsSlots with a code (A1, B2), a product, a price in cents and a count
MoneyAccepts 5¢, 10¢, 25¢ and $1 coins; balance kept in integer cents
BuyingInsert coins, select a slot; the machine dispenses and returns change
ChangePaid from a limited coin box; if exact change can't be made, refuse the sale and say "Exact change only"
CancelBefore dispensing, return the customer's coins
FailuresSold out, not enough money, unknown slot; a stuck item refunds the customer
TechnicianService mode to restock slots and load coins; refused while a customer is mid-purchase

Out of scope (say it): card and phone payments, notes, multi-item baskets, telemetry to a server, temperature control. You will offer cards as an extension.

2. Find the entities

Machine, slots, products, coins and a current state

  1. From the requirements we find the classes: the machine itself, slots that hold products, products with prices, and coins. The machine also has a current state.
  • Nouns → classes: VendingMachine, Slot, Product, Coin, and the machine's state.
  • Verbs → methods: insert a coin, select a slot, cancel, dispense, give change, restock.
  • Hardware events are verbs too: the drop sensor reports itemDropped() or dispenseFailed(). Modelling them is what makes the Dispensing state real instead of decorative.

Two money containers matter, and separating them is the key modelling decision:

  • Escrow: the coins this customer has inserted, kept apart until the sale completes. Cancel returns these exact coins, which is what real coin mechanisms do.
  • Coin box: the machine's own coins, used to give change. Escrowed coins join it only when a sale completes.

3. The class design

Class / typeKindResponsibility
CoinenumDenominations with their value in cents
Productvalue objectName and price in cents
SlotentityCode, product, count
VendingStateinterfaceOne method per event: insert, select, cancel, itemDropped, dispenseFailed
IdleState, HasMoneyState, DispensingState, OutOfServiceStatestatesThe rules for each mode, and the transitions
VendingMachinecontextHolds slots, escrow, coin box and the current state; forwards every event to the state
makeChangefunctionBounded change-making from the available coins

The state-by-event table, which is worth drawing before any code:

Stateinsert coinselectcancelitem droppeddispense failed
Idleescrow it → HasMoney"Insert money first"nothingerrorerror
HasMoneyescrow itchecks pass → Dispensing; otherwise show whyrefund → Idleerrorerror
Dispensingreturn coin"Please wait"ignoredcomplete sale, give change → Idlerefund → Idle
OutOfServicereturn coin"Out of service"nothingerrorerror

Why each pattern is there:

  • State for the machine's modes: every event behaves differently per state, and the rules for one state live in one class. Default methods refuse everything, so each state only writes what it allows. (See the State pattern.)
  • Integer cents and an enum for coins: money is never floating point.
  • A separate change-making function: it is pure, so it can be tested on its own, and it is the part that's easiest to get wrong.

HasMoneyState checks the slot and the balance before dispensing

  1. With the State pattern, the machine forwards insert() and select() to its current state. IdleState refuses a selection, HasMoneyState checks the price, DispensingState ignores coins until the snack drops.

The figure shows a simplified select that dispenses and returns to Idle in one go. The full code below waits in DispensingState until the drop sensor confirms the item fell, and it also checks that change can be made before committing.

4. Change-making: why greedy is not enough

The obvious algorithm is greedy: give the largest coin that fits, repeat. With an unlimited supply of US coins greedy is optimal. With a limited coin box it can fail when an answer exists:

  • Change due: 30¢. Coin box: one quarter, three dimes, no nickels.
  • Greedy takes the quarter, then needs 5¢, and has no nickel: "can't make change".
  • But three dimes work.

The fix is a tiny backtracking search: try the largest coin first with as many as possible, and if the rest can't be paid, use one fewer and try again. With four denominations and amounts of a few dollars, this explores at most a few hundred combinations, well under a millisecond. It finds a solution whenever one exists; it prefers large coins but does not guarantee the absolute minimum number of coins (a dynamic-programming version does, if the interviewer asks).

Cents, largest coins first, and refund on failure

  1. Money needs care. Keep the balance in whole cents, never floating-point dollars. Give change with the largest coins first. And if anything fails, a sold-out slot or not enough money, refund what was inserted.

The machine must run this check before it starts the motor. Selling the snack and then discovering it can't give change leaves the customer short.

5. The code

import java.util.*;

// ---------- Demo ----------
public class VendingDemo {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine();
        m.enterService();
        m.restock("A1", new Product("Chips", 170), 2);
        m.restock("B2", new Product("Water", 100), 1);
        m.loadCoins(Coin.QUARTER, 1);
        m.loadCoins(Coin.DIME, 3);                     // no nickels: greedy change would fail below
        m.leaveService();

        System.out.println("1. Select before paying");
        m.select("A1");

        System.out.println("2. Chips (170) with two dollars: change 30");
        m.insert(Coin.DOLLAR); m.insert(Coin.DOLLAR);
        m.select("A1");
        m.insert(Coin.QUARTER);                        // arrives while dispensing: returned
        m.itemDropped();

        System.out.println("3. Not enough money, then cancel");
        m.insert(Coin.QUARTER);
        m.select("B2");
        m.cancel();

        System.out.println("4. Water, exact money, then sold out");
        m.insert(Coin.DOLLAR); m.select("B2"); m.itemDropped();
        m.insert(Coin.DOLLAR); m.select("B2"); m.cancel();

        System.out.println("5. Chips with two dollars again: the box can't make 30 now");
        m.insert(Coin.DOLLAR); m.insert(Coin.DOLLAR);
        m.select("A1");
        m.cancel();

        System.out.println("6. Item stuck: full refund");
        m.insert(Coin.DOLLAR); m.insert(Coin.QUARTER); m.insert(Coin.QUARTER); m.insert(Coin.DIME); m.insert(Coin.DIME);
        m.select("A1");
        m.dispenseFailed();
        System.out.println("state: " + m.stateName());
    }
}

// ---------- Values ----------
enum Coin {
    NICKEL(5), DIME(10), QUARTER(25), DOLLAR(100);
    final int cents;
    Coin(int cents) { this.cents = cents; }
}

record Product(String name, int priceCents) {}

final class Slot {
    final String code; Product product; int count;
    Slot(String code, Product product, int count) { this.code = code; this.product = product; this.count = count; }
}

// ---------- States ----------
interface VendingState {
    default void insert(VendingMachine m, Coin c)  { m.show("Coin not accepted now"); m.returnCoins(List.of(c)); }
    default void select(VendingMachine m, String code) { m.show("Please wait"); }
    default void cancel(VendingMachine m)          { }
    default void itemDropped(VendingMachine m)     { throw new IllegalStateException("no sale in progress"); }
    default void dispenseFailed(VendingMachine m)  { throw new IllegalStateException("no sale in progress"); }
}

final class IdleState implements VendingState {
    public void insert(VendingMachine m, Coin c) { m.addToEscrow(c); m.setState(new HasMoneyState()); }
    public void select(VendingMachine m, String code) { m.show("Insert money first"); }
}

final class HasMoneyState implements VendingState {
    public void insert(VendingMachine m, Coin c) { m.addToEscrow(c); }
    public void select(VendingMachine m, String code) {
        Slot s = m.slot(code);
        if (s == null)      { m.show("No such slot " + code); return; }
        if (s.count == 0)   { m.show("Sold out"); return; }
        int price = s.product.priceCents(), balance = m.balance();
        if (balance < price) { m.show("Insert " + (price - balance) + " more"); return; }
        Map<Coin, Integer> change = m.planChange(balance - price);
        if (change == null) { m.show("Exact change only"); return; }
        m.startSale(s, change);                       // motor starts; wait for the drop sensor
        m.setState(new DispensingState());
    }
    public void cancel(VendingMachine m) { m.refundEscrow(); m.setState(new IdleState()); }
}

final class DispensingState implements VendingState {
    // insert/select/cancel use the defaults: coins are returned, keys are ignored
    public void itemDropped(VendingMachine m)    { m.completeSale();  m.setState(new IdleState()); }
    public void dispenseFailed(VendingMachine m) { m.show("Item stuck, refunding"); m.refundEscrow(); m.setState(new IdleState()); }
}

final class OutOfServiceState implements VendingState {
    public void select(VendingMachine m, String code) { m.show("Out of service"); }
}

// ---------- The machine (context) ----------
final class VendingMachine {
    private final Map<String, Slot> slots = new LinkedHashMap<>();
    private final EnumMap<Coin, Integer> coinBox = new EnumMap<>(Coin.class); // coins kept for change
    private final List<Coin> escrow = new ArrayList<>();                     // this customer's coins
    private VendingState state = new IdleState();
    private Slot saleSlot; private Map<Coin, Integer> saleChange;

    VendingMachine() { for (Coin c : Coin.values()) coinBox.put(c, 0); }

    // Events from the hardware. synchronized: coin acceptor, keypad and drop sensor are separate threads.
    synchronized void insert(Coin c)        { state.insert(this, c); }
    synchronized void select(String code)   { state.select(this, code); }
    synchronized void cancel()              { state.cancel(this); }
    synchronized void itemDropped()         { state.itemDropped(this); }
    synchronized void dispenseFailed()      { state.dispenseFailed(this); }

    // Technician operations, allowed only when nobody is mid-purchase
    synchronized void enterService() { requireIdle(); state = new OutOfServiceState(); }
    synchronized void leaveService() { if (state instanceof OutOfServiceState) state = new IdleState(); }
    synchronized void restock(String code, Product p, int count) {
        if (!(state instanceof OutOfServiceState)) throw new IllegalStateException("enter service mode first");
        slots.put(code, new Slot(code, p, count));
    }
    synchronized void loadCoins(Coin c, int n) {
        if (!(state instanceof OutOfServiceState)) throw new IllegalStateException("enter service mode first");
        coinBox.merge(c, n, Integer::sum);
    }
    private void requireIdle() { if (!(state instanceof IdleState)) throw new IllegalStateException("customer mid-purchase"); }

    // ---- helpers the states call ----
    void setState(VendingState s) { state = s; }
    String stateName() { return state.getClass().getSimpleName(); }
    Slot slot(String code) { return slots.get(code); }
    int balance() { return escrow.stream().mapToInt(c -> c.cents).sum(); }
    void addToEscrow(Coin c) { escrow.add(c); }
    void show(String msg) { System.out.println("  [display] " + msg); }
    void returnCoins(Collection<Coin> coins) { if (!coins.isEmpty()) System.out.println("  [tray] " + coins); }

    void refundEscrow() { returnCoins(escrow); escrow.clear(); }

    /** Change from the coin box plus the escrowed coins, or null if it can't be made. */
    Map<Coin, Integer> planChange(int amount) {
        EnumMap<Coin, Integer> available = new EnumMap<>(coinBox);
        for (Coin c : escrow) available.merge(c, 1, Integer::sum);
        return makeChange(amount, available);
    }

    void startSale(Slot s, Map<Coin, Integer> change) { saleSlot = s; saleChange = change; show("Dispensing " + s.product.name()); }

    void completeSale() {
        saleSlot.count--;
        for (Coin c : escrow) coinBox.merge(c, 1, Integer::sum);           // escrow goes into the box
        List<Coin> out = new ArrayList<>();
        saleChange.forEach((c, n) -> { coinBox.merge(c, -n, Integer::sum); out.addAll(Collections.nCopies(n, c)); });
        escrow.clear();
        returnCoins(out);
        saleSlot = null; saleChange = null;
    }

    /** Bounded change-making: try the largest coin first, back off if the rest can't be paid. */
    static Map<Coin, Integer> makeChange(int amount, Map<Coin, Integer> available) {
        Coin[] coins = Coin.values();
        Map<Coin, Integer> used = new EnumMap<>(Coin.class);
        return pay(amount, coins.length - 1, coins, available, used) ? used : null;
    }
    private static boolean pay(int left, int i, Coin[] coins, Map<Coin, Integer> avail, Map<Coin, Integer> used) {
        if (left == 0) return true;
        if (i < 0) return false;
        Coin c = coins[i];
        for (int k = Math.min(avail.getOrDefault(c, 0), left / c.cents); k >= 0; k--) {
            if (k > 0) used.put(c, k); else used.remove(c);
            if (pay(left - k * c.cents, i - 1, coins, avail, used)) return true;
        }
        used.remove(c);
        return false;
    }
}

Both print:

1. Select before paying
  [display] Insert money first
2. Chips (170) with two dollars: change 30
  [display] Dispensing Chips
  [display] Coin not accepted now
  [tray] [QUARTER]
  [tray] [DIME, DIME, DIME]
3. Not enough money, then cancel
  [display] Insert 75 more
  [tray] [QUARTER]
4. Water, exact money, then sold out
  [display] Dispensing Water
  [display] Sold out
  [tray] [DOLLAR]
5. Chips with two dollars again: the box can't make 30 now
  [display] Exact change only
  [tray] [DOLLAR, DOLLAR]
6. Item stuck: full refund
  [display] Dispensing Chips
  [display] Item stuck, refunding
  [tray] [DOLLAR, QUARTER, QUARTER, DIME, DIME]
state: IdleState

Walk through two of these in the interview. In step 2 the box holds one quarter and three dimes; greedy would fail, the search returns three dimes, and the quarter inserted mid-dispense is pushed straight back. In step 5 the box has no dimes left, so 30¢ can't be made from a quarter and dollars; the sale is refused before anything drops and the customer's own two dollars come back.

6. Concurrency

A vending machine has one customer at a time, so why talk about threads? Because the events come from different hardware: the coin acceptor raises an interrupt, the keypad has its own handler, the drop sensor fires independently, and a technician or a remote management service may call restock. Without protection, a coin can arrive while select is half-way through computing change.

RaceWhat goes wrongFix in the code above
Coin arrives during selectChange is computed from a balance that has just changedEvery event runs under one lock (synchronized / threading.Lock), so events are handled one at a time
Restock while a sale is in progressSlot replaced while its count is being decrementedRestock only allowed in OutOfServiceState, entered only from Idle
Two quick presses of A1Two items for one paymentThe first select moves to Dispensing, whose select just says "Please wait"
Sensor reports "dropped" twiceChange given twiceitemDropped is only valid in Dispensing; the second one hits the default and is rejected

The lock is coarse and that's correct here: each event takes microseconds, and there is one customer. Real embedded controllers often go one step further and use a single event loop: every interrupt puts an event on a queue, and one thread takes events off it in order. That gives the same one-at-a-time guarantee without locks, and it's a good thing to mention.

7. Extensions the interviewer will ask for

New payment methods slot in behind an interface

  1. Finally, think about change requests. Card payments, a refill mode for technicians, or a “maintenance” state are all easy to add when each state and each payment method is its own class.
  • Card or phone payment: a PaymentMethod interface (authorise, capture, voidAuth). Coins become one implementation; HasMoneyState asks the payment method whether enough is authorised. The states don't change shape.
  • Maintenance and refill mode: already there as OutOfServiceState; add a PIN check on entering it.
  • Multi-item basket: a Basket in the context and a checkout event; select adds to it in a new Selecting state.
  • Discounts or happy-hour pricing: a PricingStrategy consulted when a slot is selected. The price is fixed at selection time.
  • Low-stock alerts: the Observer pattern: the machine publishes "slot A1 has 2 left", and a telemetry module subscribes.
  • Notes as well as coins: a Note type that can be accepted but never given as change; the change-making function only uses the coin box.

When not to over-design

  • A machine with one product and exact-price tokens (a car wash) needs a counter and a boolean, not four state classes.
  • If the interviewer only wants the money logic, spend your time on cents, escrow and change-making, and say the states would be a switch on an enum for now.
  • Don't build the fleet server unless asked; one sentence about "prices are applied in Idle" covers it.

In the interview

Your turn: spot the bug

A candidate's HasMoneyState.select is below. Find at least three bugs and fix them.

public void select(VendingMachine m, String code) {
    Slot s = m.slot(code);
    if (m.balance() >= s.price()) {
        s.count--;
        m.dispense(s);
        m.giveChange(m.balance() - s.price());     // greedy, largest coins first
        m.setState(new IdleState());
    }
}
Compare with our answer

The bugs: (1) no null check for an unknown code, and no sold-out check, so count can go negative and the customer pays for nothing; (2) no message when the balance is too low, so the customer doesn't know what to do; (3) change is given greedily after dispensing, so a box that can't make change still sells the item; (4) the count is decremented before the item drops, so a stuck item is lost from the inventory and the customer isn't refunded; (5) the balance is never cleared, so the next customer inherits it.

public void select(VendingMachine m, String code) {
    Slot s = m.slot(code);
    if (s == null)     { m.show("No such slot " + code); return; }
    if (s.count == 0)  { m.show("Sold out"); return; }
    int price = s.product.priceCents(), balance = m.balance();
    if (balance < price) { m.show("Insert " + (price - balance) + " more"); return; }
    Map<Coin, Integer> change = m.planChange(balance - price);     // check BEFORE dispensing
    if (change == null) { m.show("Exact change only"); return; }
    m.startSale(s, change);                                        // count and escrow settle on itemDropped()
    m.setState(new DispensingState());
}

A strong answer mentions: unknown slot and sold-out checks · a message when money is short · change planned before dispensing · inventory and escrow settled only when the drop sensor confirms · the balance cleared after the sale · not using a double anywhere.

Your turn: the requirement changes

The operator adds contactless card payment. A card tap should authorise the item's price, and the customer must never be charged for an item that doesn't drop. Coins must keep working. What changes in the design?

Compare with our answer

A strong answer mentions:

  • A PaymentMethod interface with authorise(cents), capture() and voidAuth(); CoinPayment wraps the escrow, CardPayment calls the card reader.
  • A new state, Authorising, entered when a card is tapped after a selection, because the reader answers asynchronously; it refuses coins and other selections.
  • Capture only on itemDropped; void on dispenseFailed or a timeout, so the customer is never charged for a stuck item.
  • No change-making for cards; the price is fixed at selection time.
  • A declined or timed-out authorisation returns to Idle with a message; the card reader's callback arriving after a timeout must be ignored (check it matches the current sale).
  • The existing coin states stay as they are: that is the payoff of one class per state.
Vending machine on one page
  • States: Idle → HasMoney → Dispensing → Idle; OutOfService for technicians. Draw the state × event table first.
  • Refuse by default: the interface's default methods return coins and ignore keys; each state overrides only what it allows.
  • Money: integer cents; Coin enum; escrow (customer's coins) separate from the coin box (change).
  • Change-making: limited coins break greedy (30¢ from 25+10+10+10); use backtracking or DP, and check before dispensing.
  • Dispensing: wait for the drop sensor; stuck item → refund; timeout → treat as failure.
  • Concurrency: hardware events on different threads → one lock or one event queue; restock only in service mode.
  • Real-world: persist escrow across power cuts; cards authorise, capture after drop, void on failure.
  • Extensions: PaymentMethod interface, PricingStrategy, Observer for low-stock alerts.
Interactive labPractise it: run the machine and add a new payment methodOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A machine's coin box holds one quarter and three dimes and no nickels. A customer is owed 30¢. What should a correct change-making routine do?

2. Why should the machine work out the change before it starts the dispensing motor?

3. In the State design, a customer inserts a quarter while a snack is falling. What happens?

4. A candidate stores the balance as a double of dollars. Which bug is most likely to follow?

5. The drop sensor never reports either success or failure after a sale starts. What should the design include?

6. Coin acceptor, keypad and drop sensor each deliver events on their own thread. Which approach keeps the machine's state consistent?

7. A card payment is added. When should the machine actually take the customer's money?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.