Design a Vending Machine in Java

A vending machine is the classic state-pattern exercise, and the interview framework fits it well: the states are few and obvious, money handling forces a decision about representation, and the hard part hides in a detail most candidates skip, which is making change when the machine's coins are limited. This article designs it in Java and ends with a complete program.

Requirements

Functional requirements

The machine holds products in numbered slots. Each slot has a name, a price and a quantity.
A customer inserts coins (nickel 5, dime 10, quarter 25, dollar 100 cents), selects a slot, and receives the product plus change.
If the credit is too low, the slot is sold out or unknown, the selection is refused and the credit stays.
A customer can ask for a refund and gets back exactly the coins inserted.
Staff can restock slots, load coins into the change bank, and put the machine out of service.

Rules and assumptions

Money is integer cents. Coins are a closed set, so they are an enum.
The coins a customer inserts join the change bank when a sale completes, so they can be used as change later.
If the machine cannot make the exact change, the sale is refused and nothing changes.
Out of scope: cards, bills, temperature, hardware faults. Card payment appears in the extensions.

Entities and relationships

Noun	Kind of thing	Java form
Coin	one of a fixed set with a value	`enum Coin`
Money	an amount	`record Money(int cents)`
Slot	an identifier	`record Slot(int id)`
Stock	data: name, price, quantity	`record Stock` in a `Map<Slot, Stock>`
Coin bank	how many of each coin	`Map<Coin, Integer>` (an `EnumMap`)
Machine state	idle, collecting money, out of service	`sealed interface State` with a record per state

The state type is where the design has a choice. A customer's inserted coins exist only while a purchase is in progress, so they live inside the Collecting record. The credit is not stored separately: it is the sum of those coins. Storing both a credit field and a coin list would allow them to disagree. One source of truth is the rule from encapsulation and invariants.

classDiagram
    class VendingMachine {
        -inventory: Map~Slot, Stock~
        -bank: Map~Coin, Integer~
        -state: State
        +insertCoin(coin) Money
        +select(slot) Dispensed
        +refund() List~Coin~
        +restock(slot, name, price, quantity)
    }
    class State {
        <<sealed interface>>
        Idle
        Collecting(coins)
        OutOfService
    }
    class Stock {
        <<record>>
        +name: String
        +price: Money
        +quantity: int
    }
    class Coin {
        <<enumeration>>
        NICKEL
        DIME
        QUARTER
        DOLLAR
    }
    VendingMachine "1" *-- "many" Stock
    VendingMachine --> State
    State ..> Coin
    VendingMachine ..> Coin

API

Java

final class VendingMachine {
    Money insertCoin(Coin coin);
    Dispensed select(Slot slot);
    List<Coin> refund();
    void restock(Slot slot, String name, Money price, int quantity);
    List<Coin> outOfService();
}

// Every refusal is a VendException carrying one of these values.
sealed interface VendError {
    enum Plain implements VendError { OUT_OF_SERVICE, CANNOT_MAKE_CHANGE, NOTHING_TO_REFUND }
    record UnknownSlot(Slot slot) implements VendError {}
    record SoldOut(Slot slot) implements VendError {}
    record InsufficientCredit(Money price, Money credit) implements VendError {}
}

Each operation that a customer performs returns what the customer gets: the credit so far, the product with its change, the refunded coins. Returning coins as values, instead of printing "returning 25 cents", keeps the core free of output and simple to test.

Refusals are exceptions, because a refused operation must stop before it changes anything, and the caller then has no half-finished state to inspect. The exception is unchecked and carries a sealed VendError, so a caller can still branch on the reason with an exhaustive switch.

Design decisions

The state is a sealed interface. The states are Idle, Collecting(coins) and OutOfService. Each operation is a switch on the state, so a missing case is a compile error, and the meaning of every operation in every state is visible in one place. The table lists it.

Operation	Idle	Collecting	OutOfService
insert coin	start collecting	add coin	refused
select	refused: no credit	sell if credit, stock and change allow	refused
refund	nothing to refund	return the coins, go idle	refused
out of service	switch	refund, then switch	no change

Here the states differ in the data they carry and the operations they allow, which is the sign a sealed type fits. A design with one class per state would also work, but the machine is a long-lived shared object that a UI holds for hours, so a field that changes its state value is more practical. See state machines with sealed types for the trade-off.

Change making is a search, not a greedy loop. With an unlimited supply of US coins, taking the largest coin first is optimal. A real machine has a limited bank. Suppose 30 cents of change is due and the bank holds one quarter and three dimes. Greedy takes the quarter, needs 5 more and has no nickel, so it fails, although three dimes work. The design uses a small recursive search over denominations from largest to smallest, trying to take as many of each as the bank allows and backtracking. It returns the first solution found, which uses the largest coins first, and an empty Optional if no combination exists.

Sales are all or nothing. select works on a trial copy of the bank (the current bank plus the customer's coins). Only if change is possible does it commit: the trial bank replaces the real bank, the quantity drops by one, and the state returns to idle. On every error path nothing has changed, so the customer's credit is intact and a refund still works.

Refunds return the original coins. Because the coins are kept in the Collecting record, a refund hands that list back. The bank is only updated at the moment of a completed sale, so a refund can never give away coins the bank needed.

IDs and validation. Slots are a record, so a slot cannot be confused with a quantity. An unknown slot is a domain error, not a NullPointerException.

The state machine on its own

This program shows the transition rules without any money, to check the table above. The switch expressions over the two enums have no default branch, so adding a state or an event forces an update.

Java

import java.util.List;

enum Kind { IDLE, COLLECTING, OUT_OF_SERVICE }

enum Event { INSERT, SELL_OK, REFUND, SERVICE_ON, SERVICE_OFF }

sealed interface Transition {
    record To(Kind state) implements Transition {}

    record Refused(String reason) implements Transition {}
}

public class Main {
    static Transition next(Kind state, Event event) {
        return switch (state) {
            case IDLE -> switch (event) {
                case INSERT -> new Transition.To(Kind.COLLECTING);
                case SELL_OK -> new Transition.Refused("no credit");
                case REFUND -> new Transition.Refused("nothing to refund");
                case SERVICE_ON -> new Transition.To(Kind.OUT_OF_SERVICE);
                case SERVICE_OFF -> new Transition.To(Kind.IDLE);
            };
            case COLLECTING -> switch (event) {
                case INSERT -> new Transition.To(Kind.COLLECTING);
                case SELL_OK, REFUND -> new Transition.To(Kind.IDLE);
                case SERVICE_ON -> new Transition.To(Kind.OUT_OF_SERVICE);
                case SERVICE_OFF -> new Transition.To(Kind.COLLECTING);
            };
            case OUT_OF_SERVICE -> switch (event) {
                case INSERT, SELL_OK, REFUND -> new Transition.Refused("out of service");
                case SERVICE_ON -> new Transition.To(Kind.OUT_OF_SERVICE);
                case SERVICE_OFF -> new Transition.To(Kind.IDLE);
            };
        };
    }

    public static void main(String[] args) {
        var script = List.of(Event.INSERT, Event.INSERT, Event.SELL_OK, Event.REFUND, Event.INSERT,
            Event.SERVICE_ON, Event.INSERT, Event.SERVICE_OFF);
        var state = Kind.IDLE;
        for (Event event : script) {
            switch (next(state, event)) {
                case Transition.To(var newState) -> {
                    System.out.println(state + " + " + event + " -> " + newState);
                    state = newState;
                }
                case Transition.Refused(var reason) ->
                    System.out.println(state + " + " + event + " refused: " + reason);
            }
        }
    }
}

Output

IDLE + INSERT -> COLLECTING
COLLECTING + INSERT -> COLLECTING
COLLECTING + SELL_OK -> IDLE
IDLE + REFUND refused: nothing to refund
IDLE + INSERT -> COLLECTING
COLLECTING + SERVICE_ON -> OUT_OF_SERVICE
OUT_OF_SERVICE + INSERT refused: out of service
OUT_OF_SERVICE + SERVICE_OFF -> IDLE

Making change

The change routine is the part worth testing in isolation. It takes the amount due and a bank of available coins and returns a list of coins, or an empty Optional. The program compares it with a greedy loop on the 30 cent example.

Java

import java.util.ArrayList;
import java.util.EnumMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;

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

    static final List<Coin> DESCENDING = List.of(values()).reversed();

    private final int cents;

    Coin(int cents) {
        this.cents = cents;
    }

    int cents() {
        return cents;
    }
}

public class Main {
    static Optional<List<Coin>> greedy(int amount, Map<Coin, Integer> bank) {
        var out = new ArrayList<Coin>();
        for (Coin coin : Coin.DESCENDING) {
            int available = bank.getOrDefault(coin, 0);
            while (amount >= coin.cents() && available > 0) {
                amount -= coin.cents();
                available--;
                out.add(coin);
            }
        }
        return amount == 0 ? Optional.of(out) : Optional.empty();
    }

    static Optional<List<Coin>> exact(int amount, Map<Coin, Integer> bank) {
        var out = new ArrayList<Coin>();
        return go(amount, 0, bank, out) ? Optional.of(out) : Optional.empty();
    }

    private static boolean go(int amount, int index, Map<Coin, Integer> bank, List<Coin> out) {
        if (amount == 0) {
            return true;
        }
        if (index == Coin.DESCENDING.size()) {
            return false;
        }
        Coin coin = Coin.DESCENDING.get(index);
        int most = Math.min(amount / coin.cents(), bank.getOrDefault(coin, 0));
        for (int take = most; take >= 0; take--) {
            int before = out.size();
            for (int i = 0; i < take; i++) {
                out.add(coin);
            }
            if (go(amount - take * coin.cents(), index + 1, bank, out)) {
                return true;
            }
            out.subList(before, out.size()).clear(); // backtrack
        }
        return false;
    }

    public static void main(String[] args) {
        var bank = new EnumMap<Coin, Integer>(Map.of(Coin.QUARTER, 1, Coin.DIME, 3));
        System.out.println("greedy 30: " + greedy(30, bank));
        System.out.println("exact  30: " + exact(30, bank));
        System.out.println("exact  35: " + exact(35, bank));
        System.out.println("exact  40: " + exact(40, bank));
        System.out.println("exact   5: " + exact(5, bank));
    }
}

Output

greedy 30: Optional.empty
exact  30: Optional[[DIME, DIME, DIME]]
exact  35: Optional[[QUARTER, DIME]]
exact  40: Optional.empty
exact   5: Optional.empty

Greedy fails on 30 while the search finds three dimes. For 35 the search finds a quarter and a dime, and for 5 it correctly reports that no combination exists because the bank has no nickels. The search is exponential in the worst case, but with four denominations and small counts it is instant. A machine with many denominations would use dynamic programming over the amount instead.

Full implementation

Java

import java.util.ArrayList;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.function.Supplier;

record Money(int cents) {
    Money {
        if (cents < 0) {
            throw new IllegalArgumentException("money cannot be negative");
        }
    }

    @Override
    public String toString() {
        return "$%d.%02d".formatted(cents / 100, cents % 100);
    }
}

record Slot(int id) {}

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

    static final List<Coin> DESCENDING = List.of(values()).reversed();

    private final int cents;

    Coin(int cents) {
        this.cents = cents;
    }

    int cents() {
        return cents;
    }
}

sealed interface VendError {
    enum Plain implements VendError { OUT_OF_SERVICE, CANNOT_MAKE_CHANGE, NOTHING_TO_REFUND }

    record UnknownSlot(Slot slot) implements VendError {}

    record SoldOut(Slot slot) implements VendError {}

    record InsufficientCredit(Money price, Money credit) implements VendError {}
}

final class VendException extends RuntimeException {
    private final VendError error;

    VendException(VendError error) {
        super(error.toString());
        this.error = error;
    }

    VendError error() {
        return error;
    }
}

record Stock(String name, Money price, int quantity) {}

record Dispensed(String product, List<Coin> change) {
    Dispensed {
        change = List.copyOf(change);
    }
}

sealed interface State {
    record Idle() implements State {}

    record Collecting(List<Coin> coins) implements State {
        public Collecting {
            coins = List.copyOf(coins);
        }
    }

    record OutOfService() implements State {}
}

final class VendingMachine {
    private final Map<Slot, Stock> inventory = new HashMap<>();
    private Map<Coin, Integer> bank = new EnumMap<>(Coin.class);
    private State state = new State.Idle();

    static Money total(List<Coin> coins) {
        return new Money(coins.stream().mapToInt(Coin::cents).sum());
    }

    /** Finds coins that add up to the amount using the bank, largest coins first. */
    static Optional<List<Coin>> makeChange(Money amount, Map<Coin, Integer> bank) {
        var out = new ArrayList<Coin>();
        return search(amount.cents(), 0, bank, out) ? Optional.of(out) : Optional.empty();
    }

    private static boolean search(int amount, int index, Map<Coin, Integer> bank, List<Coin> out) {
        if (amount == 0) {
            return true;
        }
        if (index == Coin.DESCENDING.size()) {
            return false;
        }
        Coin coin = Coin.DESCENDING.get(index);
        int most = Math.min(amount / coin.cents(), bank.getOrDefault(coin, 0));
        for (int take = most; take >= 0; take--) {
            int before = out.size();
            for (int i = 0; i < take; i++) {
                out.add(coin);
            }
            if (search(amount - take * coin.cents(), index + 1, bank, out)) {
                return true;
            }
            out.subList(before, out.size()).clear();
        }
        return false;
    }

    void restock(Slot slot, String name, Money price, int quantity) {
        if (quantity < 0) {
            throw new IllegalArgumentException("quantity cannot be negative");
        }
        inventory.put(slot, new Stock(name, price, quantity));
    }

    void loadCoins(Coin coin, int count) {
        if (count < 0) {
            throw new IllegalArgumentException("count cannot be negative");
        }
        bank.merge(coin, count, Integer::sum);
    }

    Money insertCoin(Coin coin) {
        return switch (state) {
            case State.OutOfService out -> throw new VendException(VendError.Plain.OUT_OF_SERVICE);
            case State.Idle idle -> {
                state = new State.Collecting(List.of(coin));
                yield total(List.of(coin));
            }
            case State.Collecting collecting -> {
                var coins = new ArrayList<>(collecting.coins());
                coins.add(coin);
                state = new State.Collecting(coins);
                yield total(coins);
            }
        };
    }

    Dispensed select(Slot slot) {
        List<Coin> inserted = switch (state) {
            case State.OutOfService out -> throw new VendException(VendError.Plain.OUT_OF_SERVICE);
            case State.Idle idle -> List.of();
            case State.Collecting collecting -> collecting.coins();
        };
        Stock stock = inventory.get(slot);
        if (stock == null) {
            throw new VendException(new VendError.UnknownSlot(slot));
        }
        if (stock.quantity() == 0) {
            throw new VendException(new VendError.SoldOut(slot));
        }
        Money credit = total(inserted);
        if (credit.cents() < stock.price().cents()) {
            throw new VendException(new VendError.InsufficientCredit(stock.price(), credit));
        }

        // Work on a trial bank so that a failure leaves everything untouched.
        var trial = new EnumMap<Coin, Integer>(bank);
        for (Coin coin : inserted) {
            trial.merge(coin, 1, Integer::sum);
        }
        var change = makeChange(new Money(credit.cents() - stock.price().cents()), trial)
            .orElseThrow(() -> new VendException(VendError.Plain.CANNOT_MAKE_CHANGE));
        for (Coin coin : change) {
            trial.merge(coin, -1, Integer::sum);
        }

        bank = trial;
        state = new State.Idle();
        inventory.put(slot, new Stock(stock.name(), stock.price(), stock.quantity() - 1));
        return new Dispensed(stock.name(), change);
    }

    List<Coin> refund() {
        return switch (state) {
            case State.OutOfService out -> throw new VendException(VendError.Plain.OUT_OF_SERVICE);
            case State.Idle idle -> throw new VendException(VendError.Plain.NOTHING_TO_REFUND);
            case State.Collecting collecting -> {
                state = new State.Idle();
                yield collecting.coins();
            }
        };
    }

    List<Coin> outOfService() {
        List<Coin> returned = state instanceof State.Collecting collecting ? collecting.coins() : List.of();
        state = new State.OutOfService();
        return returned;
    }

    void backInService() {
        if (state instanceof State.OutOfService) {
            state = new State.Idle();
        }
    }

    Money credit() {
        return state instanceof State.Collecting collecting ? total(collecting.coins()) : new Money(0);
    }

    Money bankValue() {
        int sum = 0;
        for (var entry : bank.entrySet()) {
            sum += entry.getKey().cents() * entry.getValue();
        }
        return new Money(sum);
    }
}

public class Main {
    /** Runs one operation and shows either its result or the error it threw. */
    static String show(Supplier<?> action) {
        try {
            return "Ok(" + action.get() + ")";
        } catch (VendException e) {
            return "Err(" + e.error() + ")";
        }
    }

    public static void main(String[] args) {
        var machine = new VendingMachine();
        machine.restock(new Slot(1), "Chips", new Money(135), 2);
        machine.restock(new Slot(2), "Gum", new Money(60), 1);
        machine.restock(new Slot(3), "Soda", new Money(125), 0);
        machine.loadCoins(Coin.QUARTER, 2);
        machine.loadCoins(Coin.DIME, 3);
        machine.loadCoins(Coin.NICKEL, 1);

        System.out.println("select with no credit: " + show(() -> machine.select(new Slot(1))));
        System.out.println("credit " + show(() -> machine.insertCoin(Coin.DOLLAR)));
        System.out.println("select chips: " + show(() -> machine.select(new Slot(1))));
        System.out.println("select soda:  " + show(() -> machine.select(new Slot(3))));
        System.out.println("select slot 9: " + show(() -> machine.select(new Slot(9))));
        System.out.println("refund: " + show(machine::refund));
        System.out.println("refund again: " + show(machine::refund));

        // 100 + 100 - 135 = 65 due: two quarters, a dime and a nickel from the bank.
        machine.insertCoin(Coin.DOLLAR);
        machine.insertCoin(Coin.DOLLAR);
        var sale = machine.select(new Slot(1));
        System.out.println("sale: " + sale.product() + " change " + sale.change() + " = " + VendingMachine.total(sale.change()));
        System.out.println("bank now " + machine.bankValue());

        // Gum costs 60, so a dollar needs 40 back. The bank now has no quarters and no
        // nickels, and two dimes are not enough, so the sale is refused.
        machine.insertCoin(Coin.DOLLAR);
        System.out.println("gum: " + show(() -> machine.select(new Slot(2))));
        System.out.println("returned " + machine.outOfService());
        System.out.println("insert while out of service: " + show(() -> machine.insertCoin(Coin.DIME)));
        machine.backInService();
        System.out.println("insert after service: " + show(() -> machine.insertCoin(Coin.DIME)));
    }
}

Output

select with no credit: Err(InsufficientCredit[price=$1.35, credit=$0.00])
credit Ok($1.00)
select chips: Err(InsufficientCredit[price=$1.35, credit=$1.00])
select soda:  Err(SoldOut[slot=Slot[id=3]])
select slot 9: Err(UnknownSlot[slot=Slot[id=9]])
refund: Ok([DOLLAR])
refund again: Err(NOTHING_TO_REFUND)
sale: Chips change [QUARTER, QUARTER, DIME, NICKEL] = $0.65
bank now $2.20
gum: Err(CANNOT_MAKE_CHANGE)
returned [DOLLAR]
insert while out of service: Err(OUT_OF_SERVICE)
insert after service: Ok($0.10)

Read the trace against the design. Selection with no credit fails without changing state. The refund returns the dollar the customer inserted, and a second refund reports NOTHING_TO_REFUND. The chips sale with two dollars gives 65 cents back, two quarters, a dime and a nickel, taken from the bank largest first. That sale drains the quarters and the nickel, so the later gum purchase with a dollar needs 40 cents back that the bank cannot form, and CANNOT_MAKE_CHANGE is returned while the dollar stays as credit until outOfService refunds it. Each failure is a VendError value inside a VendException, and the failed select calls leave the credit in place, which the successful refund afterwards proves.

Testing the change search

The change routine is pure, so it is the best candidate for unit tests. This program checks the same search with plain assert statements and small helper methods. The checker runs every example with assertions enabled, so a failed assert stops the program with an error.

Java

import java.util.ArrayList;
import java.util.EnumMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;

enum Coin {
    NICKEL(5), DIME(10), QUARTER(25);

    static final List<Coin> DESCENDING = List.of(values()).reversed();

    private final int cents;

    Coin(int cents) {
        this.cents = cents;
    }

    int cents() {
        return cents;
    }
}

public class Main {
    static Optional<List<Coin>> change(int amount, Map<Coin, Integer> bank) {
        var out = new ArrayList<Coin>();
        return go(amount, 0, bank, out) ? Optional.of(out) : Optional.empty();
    }

    private static boolean go(int amount, int i, Map<Coin, Integer> bank, List<Coin> out) {
        if (amount == 0) {
            return true;
        }
        if (i == Coin.DESCENDING.size()) {
            return false;
        }
        Coin coin = Coin.DESCENDING.get(i);
        int most = Math.min(amount / coin.cents(), bank.getOrDefault(coin, 0));
        for (int take = most; take >= 0; take--) {
            int before = out.size();
            for (int k = 0; k < take; k++) {
                out.add(coin);
            }
            if (go(amount - take * coin.cents(), i + 1, bank, out)) {
                return true;
            }
            out.subList(before, out.size()).clear();
        }
        return false;
    }

    static void zeroChangeIsEmpty() {
        assert change(0, new EnumMap<>(Coin.class)).equals(Optional.of(List.of()));
    }

    static void backtracksWhenGreedyWouldFail() {
        var bank = new EnumMap<Coin, Integer>(Map.of(Coin.QUARTER, 1, Coin.DIME, 3));
        assert change(30, bank).equals(Optional.of(List.of(Coin.DIME, Coin.DIME, Coin.DIME)));
    }

    static void reportsEmptyWhenImpossible() {
        var bank = new EnumMap<Coin, Integer>(Map.of(Coin.QUARTER, 1));
        assert change(10, bank).isEmpty();
    }

    public static void main(String[] args) {
        zeroChangeIsEmpty();
        backtracksWhenGreedyWouldFail();
        reportsEmptyWhenImpossible();
        System.out.println("3 checks passed");
    }
}

Output

3 checks passed

Extensions

Follow-up	Where the change goes
Accept cards	A `PaymentMethod` interface with `authorize(amount)` and `capture`. The `Collecting` record becomes `CollectingCash(coins)` and `CollectingCard(authorization)`. `select` switches over both.
Bills	A `Bill` enum and a stack of bills that cannot be used as change. Credit becomes the sum over both.
Sales report or low-stock alert	An observer notified on each sale. See event bus and observers.
Dynamic pricing	A `PricingStrategy` interface on the slot, as in the parking lot.
Time-out returns the coins	Inject a `Clock` and store the time of the last action in `Collecting`. A periodic `tick` refunds after a limit.
A physical dispense can fail	Add a `Dispensing(slot)` state. A failure moves to `Refunding`, so the customer never pays for nothing.
Two customers at once (a network kiosk)	Make each public method `synchronized`, or guard the machine with one `ReentrantLock`. The whole `select` is a single critical section, so the trial bank is consistent.

Two questions often come up. Why not an object per state (the classic State pattern with an interface)? For three states with small behavior, a sealed interface of records keeps the transitions in one file and makes exhaustiveness checkable. A class per state pays off when each state has large, independent behavior. Why not greedy? Because it is wrong for a limited bank, as the example shows. Say so before the interviewer asks.

Summary

Coins are an enum with a value, money is integer cents in a record, slots are a record.
The machine state is a sealed interface, Idle, Collecting(coins), OutOfService, and the credit is derived from the coins so nothing can disagree.
Each operation switches on the state, so every state and operation pair is handled explicitly and checked by the compiler.
Change making is an exact search over a limited coin bank, not a greedy loop, and it returns an empty Optional when change is impossible.
A sale works on a trial copy of the bank and commits only on success, so every error leaves the machine and the customer's credit untouched.
Refunds hand back the original coins, and all failures are values of one sealed VendError type carried by an unchecked VendException.