Design a Vending Machine

1Clarify the requirements#

Pin down what this machine does before writing a single class. The interviewer is usually happy to let you scope it, and scoping well is half the signal. Two minutes of questions here saves you from coding the wrong machine for forty.

What I ask, and why each answer is load-bearing:

• What does it sell? Slots of products, each with a price and a count. A classic grid: A1, A2, B1. I confirm a slot code maps to exactly one product, not a mix.
• How does payment work? Coins and notes, a card reader, or both? I start with cash, because change-making is the interesting part, then leave a door open for card. If there is time for one, cash is the one that tests your money skills.
• Does it give change? Yes. And it can run out of change, which is a real failure mode people forget. Taking a dollar for a 75 cent soda and owing a quarter you do not have is a correctness bug, not an edge case.
• Can the user cancel mid-transaction? Yes. Money in, then they bail: refund in full.
• Single user at a time? Physically, yes. One person, one machine. That decides the whole concurrency story, and I come back to it in section 6.

Functional scope I am committing to:

1. Select a product.
2. Insert money across multiple coins/notes.
3. Dispense the product and return correct change.
4. Cancel and refund.
5. Handle "sold out" and "insufficient funds."
6. An operator can restock products and refill the cash float.

Non-functional:

• Money correctness is non-negotiable. Never dispense without full payment, never give wrong change, never lose a cent on a cancel.
• Illegal states should be hard to reach. That is the point of the design, not a nice-to-have.
• Extensible to new payment types without rewriting the core.

2Identify the core entities#

Name the nouns that earn their place. Each maps to one real responsibility, and I can say in a line why it exists.

• VendingMachine: the context object. Holds inventory, the cash register, and the current state. Everything flows through it, so it is the one object the outside world talks to.
• State: the behavior of the machine right now (idle, has-money, dispensing, sold-out). The beating heart of the design, so it is a real abstraction, not a flag. The state owns the rules for what you can do next.
• Product: name and price. Immutable, boring, correct. Never changes once created.
• Slot (inventory entry): a product plus a quantity at a position. The machine owns a map of these keyed by code like A1.
• CashRegister: tracks how many of each denomination the machine holds, computes change, and tells us when it cannot. Every money decision lives here.
• Coin / Note (denomination): an enum of fixed values. Money is never a loose double. Integer cents everywhere.
• Transaction: the money the current user has inserted and the slot they selected. Lives only during a purchase, then it is gone.

Two things I deliberately do NOT do:

• No if (status == IDLE) branches. That scatters your rules across the codebase and guarantees a forgotten case.
• No floating-point money. 0.1 + 0.2 loses you a cent and fails you on the one property this design exists to protect.

3Class design#

The spine is the State pattern.

• VendingMachine delegates every user action (select, insert, dispense, cancel) to its current State object.
• Each state decides what is legal and what the next state is.
• "Insert money while idle" and "insert money after selecting" are different methods on different objects, not a tangle of conditionals.
• The machine never asks itself what mode it is in. It just forwards.

CashRegister is its own unit on purpose:

• Change-making is a self-contained algorithm with its own failure mode.
• Keeping it separate lets me test it in isolation and swap the strategy later without touching a single state class.

Here is the shape:

4Key implementation#

Start with money, because getting money wrong fails the round no matter how clean the rest is. If I had ten minutes of coding time, this is what I write first.

public enum Coin {
    NICKEL(5), DIME(10), QUARTER(25),
    DOLLAR(100), FIVE(500);

    public final int valueCents;
    Coin(int valueCents) { this.valueCents = valueCents; }
}

CashRegister holds a float and makes change with a greedy pass from largest to smallest.

• Greedy works for standard US denominations.
• I flag exactly when it breaks in the edge cases section, because an interviewer will probe it.

public class CashRegister {
    private final Map<Coin, Integer> floatByCoin = new EnumMap<>(Coin.class);

    public void addCoins(Map<Coin, Integer> coins) {
        coins.forEach((c, n) -> floatByCoin.merge(c, n, Integer::sum));
    }

    // Returns the exact coins to return, or empty if it can't be made.
    public Optional<Map<Coin, Integer>> makeChange(int amountCents) {
        Map<Coin, Integer> result = new EnumMap<>(Coin.class);
        int remaining = amountCents;

        List<Coin> desc = Arrays.stream(Coin.values())
            .sorted(Comparator.comparingInt((Coin c) -> c.valueCents).reversed())
            .toList();

        for (Coin coin : desc) {
            int available = floatByCoin.getOrDefault(coin, 0);
            int needed = Math.min(remaining / coin.valueCents, available);
            if (needed > 0) {
                result.put(coin, needed);
                remaining -= needed * coin.valueCents;
            }
        }
        if (remaining != 0) return Optional.empty(); // can't make exact change
        return Optional.of(result);
    }

    // Only mutate the float once we've committed to the sale.
    public void commitChange(Map<Coin, Integer> change) {
        change.forEach((c, n) -> floatByCoin.merge(c, n, (a, b) -> a - b));
    }
}

The one idea that carries this whole design:

• makeChange computes a plan without touching the float. commitChange applies it.
• That split lets me answer "can I complete this sale?" before I take any irreversible action.
• So I never land in a half-sold state where the product left but the change did not add up.

Plan the change before you touch the float. Everything else is bookkeeping.

Now the State contract and the two interesting states.

public interface State {
    void selectProduct(String code);
    void insertMoney(Coin coin);
    void dispense();
    void cancel();
}

Idle: you can select, you cannot dispense yet.

public class IdleState implements State {
    private final VendingMachine machine;
    public IdleState(VendingMachine m) { this.machine = m; }

    public void selectProduct(String code) {
        Slot slot = machine.getSlot(code);
        if (slot == null || !slot.isAvailable()) {
            throw new IllegalStateException("Product unavailable: " + code);
        }
        machine.startTransaction(slot);
        machine.setState(machine.getHasMoneyState());
    }

    public void insertMoney(Coin coin) {
        throw new IllegalStateException("Select a product first.");
    }
    public void dispense() {
        throw new IllegalStateException("Nothing selected.");
    }
    public void cancel() { /* nothing to cancel */ }
}

HasMoney: where the real logic lives. Take coins until the balance is covered, then move to dispensing.

public class HasMoneyState implements State {
    private final VendingMachine machine;
    public HasMoneyState(VendingMachine m) { this.machine = m; }

    public void selectProduct(String code) {
        throw new IllegalStateException("Transaction in progress. Cancel first.");
    }

    public void insertMoney(Coin coin) {
        Transaction tx = machine.getTransaction();
        machine.getRegister().addCoins(Map.of(coin, 1));
        tx.add(coin.valueCents);

        if (tx.insertedCents() >= tx.price()) {
            machine.setState(machine.getDispenseState());
            machine.dispense(); // auto advance once paid
        }
    }

    public void dispense() {
        throw new IllegalStateException("Insert full amount first.");
    }

    public void cancel() {
        machine.refund(machine.getTransaction().insertedCents());
        machine.endTransaction();
        machine.setState(machine.getIdleState());
    }
}

Dispense: compute change, verify we CAN make it, then commit everything or roll back.

public class DispenseState implements State {
    private final VendingMachine machine;
    public DispenseState(VendingMachine m) { this.machine = m; }

    public void dispense() {
        Transaction tx = machine.getTransaction();
        int changeDue = tx.insertedCents() - tx.price();

        Optional<Map<Coin, Integer>> change =
            machine.getRegister().makeChange(changeDue);

        if (change.isEmpty()) {
            // We can't give correct change. Refund and bail, don't half-sell.
            machine.refund(tx.insertedCents());
            machine.endTransaction();
            machine.setState(machine.getIdleState());
            throw new IllegalStateException("Exact change unavailable. Refunded.");
        }

        tx.slot().decrement();
        machine.getRegister().commitChange(change.get());
        machine.deliver(tx.slot().getProduct(), change.get());
        machine.endTransaction();

        machine.setState(machine.hasStock()
            ? machine.getIdleState()
            : machine.getSoldOutState());
    }

    public void selectProduct(String c) { throw new IllegalStateException("Busy."); }
    public void insertMoney(Coin c) { throw new IllegalStateException("Busy."); }
    public void cancel() { throw new IllegalStateException("Already dispensing."); }
}

The VendingMachine itself is thin by design. It owns the state instances, holds the current transaction, and forwards calls. No business rules, only wiring.

public class VendingMachine {
    private final Map<String, Slot> inventory;
    private final CashRegister register;
    private final State idle, hasMoney, dispense, soldOut;
    private State current;
    private Transaction transaction;

    public VendingMachine(Map<String, Slot> inventory, CashRegister register) {
        this.inventory = inventory;
        this.register = register;
        this.idle = new IdleState(this);
        this.hasMoney = new HasMoneyState(this);
        this.dispense = new DispenseState(this);
        this.soldOut = new SoldOutState(this);
        this.current = idle;
    }

    // Public API simply delegates.
    public synchronized void selectProduct(String code) { current.selectProduct(code); }
    public synchronized void insertMoney(Coin coin)      { current.insertMoney(coin); }
    public synchronized void dispense()                  { current.dispense(); }
    public synchronized void cancel()                    { current.cancel(); }

    void setState(State s) { this.current = s; }
    // ... getters for states, register, transaction helpers ...
}

One detail worth saying out loud:

• The four state objects are created once in the constructor and reused.
• They are stateless (only a back-reference to the machine), so there is no reason to allocate a new one per transition.

5Design decisions and patterns used#

Four patterns, each paying for its keep:

• State pattern (the backbone). Each state is a class with the same four methods, and the machine never asks "what mode am I in?" It just calls current.insertMoney(...). Illegal moves become loud exceptions thrown by the state that owns the rule. When the interviewer asks "what if someone dispenses before paying?", I point at HasMoneyState.dispense() and I am done. No scattered guards, no forgotten branch.
• Strategy pattern (inside CashRegister.makeChange). Greedy today, but for a weird currency or a goal of minimizing coins returned, I swap in a dynamic-programming ChangeStrategy without touching any state class. The change algorithm is isolated behind one method on purpose.
• Factory / Builder (for operators). A VendingMachineBuilder wires inventory, float, and denominations. Keeps the constructor honest and keeps setup noise out of the core.
• Enum for money (small, pays off forever). Coin carries its value, so there is no map of "this string means 25." Integer cents, never floats.

One scoping decision I make on purpose:

• Product is immutable and Transaction is short-lived.
• The only mutable, long-lived state is inventory counts and the cash float.
• That narrows where bugs can hide to two places I can name.

6Handling edge cases and concurrency#

The edge cases are where this problem is actually Medium, not Easy. Walking through them unprompted is a strong signal.

Cannot make change.

• The rule: never dispense a product if I cannot return exact change.
• Compute the change plan first. If it is empty, refund the full amount and stay honest.
• Half-selling is worse than not selling, because now the machine owes money it cannot produce.

Greedy change fails on exotic currency.

• For US coins greedy is provably optimal, so it always finds a solution if one exists.
• For arbitrary denominations (say a 20 and a 25 but no 5, where you owe 40), greedy can wrongly report failure.
• If the interviewer pushes, I switch makeChange to a DP over available counts, running in O(amount times denominations).
• I say this out loud rather than pretend greedy is universal. Claiming greedy always works is a quick way to lose credibility.

User cancels after inserting money.

• cancel() in HasMoneyState refunds everything and resets.
• The coins they inserted were already added to the float, so the refund pulls from the float.
• Edge within the edge: if they paid with a five and we refund, we must return their actual coins or an equivalent.
• I track the inserted coins on the Transaction so a refund hands back the same denominations when possible, which also avoids draining the small-coin float on every cancel.

Sold out.

• When the last unit of a slot leaves, I check hasStock().
• Whole machine empty: go to SoldOutState, which rejects selection with a clear message.
• Only that slot empty but others have stock: stay in IdleState and let selectProduct reject the empty slot specifically.
• One empty slot does not take the whole machine offline.

Concurrency (the honest take).

• A physical machine has one slot, one person. The real contention is not many buyers at once.
• It is the buyer versus the operator restocking, or a watchdog thread resetting a stuck transaction.
• I guard the public API with a single lock (synchronized on the machine) so a restock cannot interleave with a decrement.
• Coarse lock, and for one physical machine it is exactly right.
• For a server-side simulation of thousands of virtual machines, each instance still owns its own lock, so they never contend with each other.
• I would NOT reach for lock-free trickery here. It buys nothing and risks a torn money update, which is the one bug this whole design exists to prevent.

Stuck transactions.

• If a user walks away mid-purchase, a timeout thread fires cancel() after, say, 30 seconds and refunds.
• Because cancel is a normal state transition, the timeout path reuses the same safe code.
• I do not write a second, parallel refund path that can drift out of sync with the first.

7Extensions and follow-ups#

When the interviewer pushes, these are the natural next moves:

• Card and mobile payment. A PaymentMethod interface with authorize(amount) and capture(). HasMoneyState becomes a more general AwaitingPaymentState that does not care whether funds arrived as coins or an authorization. The state machine barely changes, which is the payoff of keeping payment behind an interface.
• Multiple products per purchase. A cart. Transaction grows a list of slots and a running total. Change logic is unchanged because it only cares about the final amount due.
• Observer for monitoring. Register low-stock and low-float listeners. When a slot hits zero or the quarter count drops below a threshold, notify an operator dashboard. Clean add, because inventory already funnels through the machine.
• Persistence and crash recovery. If the machine loses power mid-dispense, the "committed or not" boundary needs to be durable. I write a small transaction log: record "intend to dispense slot A1, return 2 dimes" before acting, so on restart we can finish or reverse. The plan/commit split pays off a second time here.
• Pricing rules. Happy-hour discounts become a PricingStrategy on the slot. Strategy again keeps the core untouched.

8What the interviewer is really checking#

The three things being scored:

• Behavior modeled as a state machine, not a status flag. Candidates who reach for a status enum and a wall of if checks reveal they have not internalized why the State pattern exists.
• A correctness boundary around money. Splitting "plan the change" from "commit the change" shows you think about partial failure, which is exactly the senior signal these loops reward. Type double price and a sharp interviewer notes it; integer cents and an enum of denominations say you have shipped money code before.
• Judgment on scope. Saying "one physical machine means one lock is plenty" out loud shows you match effort to the problem. Over-engineering a thread pool for a soda machine shows the opposite.

Keep the core small, make illegal states throw, and never, ever dispense without being able to give correct change.

If you liked the State machine here, the same muscle shows up in Design an ATM and Design an Elevator. For the money and change logic, compare notes with Design a Parking Lot's payment flow.