SyntaxPilot
Courses/Low-Level Design/Lesson 63
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 63 of 90

Design a vending machine

vending machine requirementsProductInventoryCoin and Note enumsVendingMachine contextstates Idle HasMoney DispensingState pattern appliedchange calculationrefundsold-out handling

These are the notes for Low-Level Design (LLD) episode 63: the vending machine, one of the most common machine-coding problems. It is really a test of one idea, states, plus careful handling of money. We gather the vending machine requirements, find the entities (Product, Inventory, Coin and Note enums, the VendingMachine context), watch the obvious String-state design swallow a customer's money, then apply the State pattern with the states Idle, HasMoney, Dispensing. Then sold-out handling, change calculation with the coins really in the machine, and refunds.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly, including exceptions. Prices, products, the coin box and the operator PIN are made up for teaching.

1. The problem: platform 3, a snack machine

Ten minutes before your train, at a snack machine on a railway platform:

What happens What went wrong in the code Fixed by
Your Rs 20 note goes in; the screen says BUSY forever The state is a String with a typo: the machine is stuck The State pattern
Someone pays for chips; the slot is empty No sold-out check; the stock went below zero Inventory with sold-out handling
Juice drops, then "change not available": the machine owes Rs 15 Change was checked after dropping, assuming every coin is in the box Change calculation before the drop, else refund
You change your mind — The coin-return lever: cancel → refund

2. Requirements

A requirement is something the system must do, agreed before coding (episode 55).

  1. Accept coins and notes; show the balance (how much has been put in so far).
  2. Choose a product by its code, like A1.
  3. Drop the product only if it is in stock and fully paid.
  4. Give exact change, from the coins really inside the machine.
  5. Until the product drops, the customer can cancel and get everything back: a refund.

The golden rule: the machine never keeps money without giving the product.

Out of scope today: restocking screens (practice 1), UPI payments, networks of machines.

Clarifying question Our assumption
Can people insert several coins and notes? Yes; the balance adds up
Which money? Coins 1, 2, 5, 10 and notes 10, 20, 50, 100 (our machine's choice)
Does the machine give change in notes? No: change only in coins, from its coin box
What if exact change is impossible? Refuse the sale and refund everything, before dropping
Can you buy two things with one balance? No: one product per sale; the rest is change

3. Entities

Entity What it is Example
Product What you buy: code, name, price A1, Chips, Rs 20
Inventory Which products are inside, and how many of each {A1=1, B2=3}
Coin, Note The money the machine accepts; each has a value in rupees Coin.FIVE = 5, Note.FIFTY = 50
VendingMachine Holds everything above, plus its current state —
State What the machine is doing right now: waiting, has money, dropping Idle, HasMoney, Dispensing

4. The obvious way: a String state (and how it breaks)

Store the state as a String and check it with if/else in every method:

class VendingMachine {                                  // the obvious way: a String state + if/else everywhere
    String state = "IDLE";  int balance = 0, chips = 2;  // chips cost Rs 20
    void insert(int amount) {
        if (state.equals("IDLE") || state.equals("HAS_MONEY")) { balance += amount; state = "HAS_MONEY"; }
        else System.out.println("busy, Rs " + amount + " ignored");
    }
    void select() {
        if (state.equals("HAS_MONEY") && balance >= 20) { state = "DISPENSING"; dispense(); }
        else if (state.equals("IDLE")) System.out.println("insert money first");
        else System.out.println("not enough money");
    }
    void dispense() {
        chips--;  balance -= 20;
        System.out.println("here are your chips. chips left: " + chips);
        state = "Idle";                                 // back to idle... (spot the bug)
    }
}
public class Main {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine();
        m.insert(20);  m.select();                      // customer 1
        m.insert(20);  m.select();                      // customer 2
        System.out.println("state = " + m.state + ", balance = " + m.balance);
    }
}

Output:

here are your chips. chips left: 1
busy, Rs 20 ignored
not enough money
state = Idle, balance = 0

Customer 1 gets chips. Then dispense() sets the state to "Idle", with small letters, while every check compares with "IDLE". The compiler can't help: to it, both are just text. From now on the machine matches no state at all: customer 2's Rs 20 is ignored, select says "not enough money", and every later customer loses money the same way. That's the swallowed note from the platform.

Why it failed

  • A String can hold any text, so a typo compiles fine and fails only at run time.
  • Every method checks every state with an if/else if chain: the rules for one state are scattered across all methods.
  • Adding a state (say, maintenance) means editing every method, and forgetting one is a new bug.

An enum would fix the typo (the compiler rejects State.Idle if the constant is IDLE), but not the scattering. For that we need the State pattern.

5. The State pattern applied

The State pattern (episode 37): each state becomes its own class, all implementing one state interface with one method per button (insert, select, cancel). The context, here VendingMachine, holds the current state object and delegates each button press to it ("delegate" = hand the work to another object). A state changes the machine's state by assigning a different state object: that's a transition.

The real-life picture is the machine's own front panel:

On the machine In the design select() means
"INSERT MONEY" light Idle "insert money first"
"SELECT ITEM Rs 30" HasMoney check, then drop
"PLEASE WAIT" Dispensing wait
The coin-return lever (same lever in every state) cancel() each state decides: refund, nothing, or too late

The transitions:

Idle ──insert──▶ HasMoney ──select (all checks pass)──▶ Dispensing ──dropped──▶ Idle
                    │  ▲ insert (more money)
                    └──cancel──▶ Idle (refund)

What each state does with each button:

insert select cancel
Idle add money → HasMoney "insert money first" "nothing to refund"
HasMoney add more money sold out? enough money? → Dispensing refund all → Idle
Dispensing "please wait" "please wait" "too late, it's dropping"
interface State { void insert(int amount); void select(); void cancel(); }     // one method per button
class VendingMachine {                                   // the context: delegates to its current state
    final State idle = new Idle(this), hasMoney = new HasMoney(this), dispensing = new Dispensing(this);
    State state = idle;  int balance = 0, chips = 1;  final int price = 20;
    void insert(int a) { state.insert(a); }   void select() { state.select(); }   void cancel() { state.cancel(); }
    void say(String s) { System.out.println(state.getClass().getSimpleName() + ": " + s); }
}
class Idle implements State { final VendingMachine m;  Idle(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.state = m.hasMoney;  m.say("balance Rs " + m.balance); }
    public void select() { m.say("insert money first"); }
    public void cancel() { m.say("nothing to refund"); } }
class HasMoney implements State { final VendingMachine m;  HasMoney(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.say("balance Rs " + m.balance); }
    public void select() {
        if (m.chips == 0) { m.say("SOLD OUT, press cancel for a refund"); return; }
        if (m.balance < m.price) { m.say("add Rs " + (m.price - m.balance)); return; }
        m.state = m.dispensing;  ((Dispensing) m.dispensing).dispense(); }
    public void cancel() { m.say("refund Rs " + m.balance);  m.balance = 0;  m.state = m.idle; } }
class Dispensing implements State { final VendingMachine m;  Dispensing(VendingMachine m) { this.m = m; }
    void dispense() { m.chips--;  m.balance -= m.price;  m.say("drop chips, change Rs " + m.balance);
                      m.balance = 0;  m.state = m.idle; }
    public void insert(int a) { m.say("please wait"); }   public void select() { m.say("please wait"); }
    public void cancel() { m.say("too late, it's dropping"); } }
public class Main { public static void main(String[] args) {
    VendingMachine m = new VendingMachine();
    m.select();  m.insert(10);  m.select();  m.insert(20);  m.select();     // customer 1
    m.insert(50);  m.select();  m.cancel();  m.cancel();                    // customer 2
}}

Output:

Idle: insert money first
HasMoney: balance Rs 10
HasMoney: add Rs 10
HasMoney: balance Rs 30
Dispensing: drop chips, change Rs 10
HasMoney: balance Rs 50
HasMoney: SOLD OUT, press cancel for a refund
HasMoney: refund Rs 50
Idle: nothing to refund

Reading it: selecting first, in Idle: "insert money first". Ten in, select: "add Rs 10". Twenty more (balance 30), select: Dispensing drops chips with Rs 10 change, back to Idle. Customer 2: Rs 50 in, but chips are now sold out: the machine stays in HasMoney so the customer can cancel, and cancel refunds Rs 50. A second cancel, in Idle: "nothing to refund".

Notes on the code:

  • VendingMachine makes one object per state and reuses them (m.state = m.hasMoney). The states keep no data of their own; the data (balance, chips) lives in the context.
  • Each state gets the machine in its constructor (Idle(VendingMachine m)), so it can read the balance and switch the state.
  • say() prints the current state's class name (getClass().getSimpleName()), which is why "balance Rs 10" is printed as HasMoney: Idle.insert switched the state before printing.
  • ((Dispensing) m.dispensing).dispense() is a cast: dispense() isn't part of the State interface (no button calls it), so we tell Java that this State really is a Dispensing.
  • State vs Strategy (episodes 34 and 37): both put behaviour behind an interface. In Strategy the caller picks the object and it rarely changes; in State the objects switch themselves as events happen.

6. Products, inventory and sold-out handling

One product isn't enough. A product is a record (episode 3): record Product(String code, String name, int price). The inventory keeps two maps (episode 4): code → product, and code → how many are left.

Sold-out handling has two parts:

  1. In HasMoney.select: if the count is 0, refuse and stay in HasMoney, so the customer can pick another product or cancel.
  2. In Inventory.take: check again and throw if the count is 0, so the count can never go below zero, even if some other code forgets the first check. Checking in the place that owns the data is called defensive programming.

Coins and notes are enums, each constant with its value. Coin.TEN and Note.TEN are different constants in different enums. Both implement one small interface, Money (int value()), so the machine can add any mix of them the same way.

find returns an Optional<Product> (episode 5): a box that may be empty, because the code might not exist (C9). The caller must ask isEmpty() before get().

import java.util.*;
interface Money { int value(); }                            // anything the machine accepts
enum Coin implements Money { ONE(1), TWO(2), FIVE(5), TEN(10);
    private final int v;  Coin(int v) { this.v = v; }   public int value() { return v; } }
enum Note implements Money { TEN(10), TWENTY(20), FIFTY(50), HUNDRED(100);
    private final int v;  Note(int v) { this.v = v; }   public int value() { return v; } }
record Product(String code, String name, int price) {}
class Inventory {                                           // what's inside, and how many of each
    private final Map<String, Product> products = new HashMap<>();
    private final Map<String, Integer> count = new TreeMap<>();
    void add(Product p, int n) { products.put(p.code(), p);  count.merge(p.code(), n, Integer::sum); }
    Optional<Product> find(String code) { return Optional.ofNullable(products.get(code)); }
    boolean soldOut(String code) { return count.getOrDefault(code, 0) == 0; }
    void take(String code) {
        if (soldOut(code)) throw new IllegalStateException(code + " is sold out");
        count.merge(code, -1, Integer::sum); }
    public String toString() { return "stock " + count; } }
public class Main { public static void main(String[] args) {   Inventory inv = new Inventory();
    inv.add(new Product("A1", "Chips", 20), 1);  inv.add(new Product("B2", "Juice", 35), 3);
    List<Money> paid = List.of(Note.TWENTY, Coin.TEN, Coin.FIVE);
    System.out.println("paid " + paid + " = Rs " + paid.stream().mapToInt(Money::value).sum());
    for (String code : List.of("B2", "A1", "A1", "C9")) {
        Optional<Product> p = inv.find(code);
        if (p.isEmpty()) System.out.println(code + ": no such product");
        else if (inv.soldOut(code)) System.out.println(code + " " + p.get().name() + ": SOLD OUT, pick another");
        else { inv.take(code);  System.out.println(code + " " + p.get().name() + ": sold, " + inv); } }
    inv.take("A1");                                         // a bug elsewhere skips the check
}}

Output:

paid [TWENTY, TEN, FIVE] = Rs 35
B2 Juice: sold, stock {A1=1, B2=2}
A1 Chips: sold, stock {A1=0, B2=2}
A1 Chips: SOLD OUT, pick another
C9: no such product
Exception in thread "main" java.lang.IllegalStateException: A1 is sold out
    at Inventory.take(Main.java:15)
    at Main.main(Main.java:27)

A TreeMap keeps the codes sorted, so the stock prints in the same order every time. The last line plays a buggy caller that skips the check: take refuses with IllegalStateException: A1 is sold out instead of letting the stock become -1.

7. Change calculation and refunds

Change = paid − price. Paid 50 for Rs 35 juice: change Rs 15.

The usual method is greedy: take the biggest coin first, as many as fit, then the next one down. Rs 15 = one 10 + one 5. (Coin lists its constants biggest first, so Coin.values() loops from 10 down to 1.)

The obvious code assumes every coin is always in the box. A real box runs out. The fix has three rules:

  1. Use only coins really in the box: take min(how many fit, how many we have) of each.
  2. Remove coins from the box only if the whole change worked.
  3. If exact change is impossible, refund, and decide that before dropping the product.
import java.util.*;
enum Coin { TEN(10), FIVE(5), TWO(2), ONE(1);  final int value;  Coin(int v) { value = v; } }   // biggest first
public class Main {
    static Map<Coin, Integer> naive(int change, Map<Coin, Integer> box) {   // greedy, never looks in the box
        Map<Coin, Integer> give = new EnumMap<>(Coin.class);
        for (Coin c : Coin.values())
            while (change >= c.value) {
                change -= c.value;  give.merge(c, 1, Integer::sum);  box.merge(c, -1, Integer::sum); }
        return give; }
    static Optional<Map<Coin, Integer>> makeChange(int change, Map<Coin, Integer> box) {
        Map<Coin, Integer> give = new EnumMap<>(Coin.class);
        for (Coin c : Coin.values()) {
            int n = Math.min(change / c.value, box.get(c));       // only coins we really have
            if (n > 0) { give.put(c, n);  change -= n * c.value; } }
        if (change != 0) return Optional.empty();                 // no exact change possible
        give.forEach((c, n) -> box.merge(c, -n, Integer::sum));   // take coins out only if it worked
        return Optional.of(give); }
    static void sell(int price, int paid, Map<Coin, Integer> box) {
        Optional<Map<Coin, Integer>> change = makeChange(paid - price, box);
        System.out.println("price " + price + ", paid " + paid + ": " + (change.isEmpty()
            ? "no exact change, REFUND Rs " + paid : "sold, change " + change.get() + ", box " + box)); }
    public static void main(String[] args) {
        Map<Coin, Integer> box = new EnumMap<>(Map.of(Coin.TEN, 1, Coin.FIVE, 0, Coin.TWO, 3, Coin.ONE, 1));
        Map<Coin, Integer> copy = new EnumMap<>(box);
        System.out.println("naive change for Rs 15: " + naive(15, copy) + ", box " + copy);
        sell(35, 50, box);                                        // change Rs 15
        sell(21, 30, box);                                        // change Rs 9
    } }

Output:

naive change for Rs 15: {TEN=1, FIVE=1}, box {TEN=0, FIVE=-1, TWO=3, ONE=1}
price 35, paid 50: sold, change {TEN=1, TWO=2, ONE=1}, box {TEN=0, FIVE=0, TWO=1, ONE=0}
price 21, paid 30: no exact change, REFUND Rs 30
  • Naive change for 15 handed out a ten and a five, and the box now holds FIVE=-1: a coin that doesn't exist. In a real machine this is the "change not available" after the drop.
  • makeChange for 15 found a ten, two twos and a one (10 + 2 + 2 + 1), and only then took them out of the box.
  • The second sale needs Rs 9, but the box has just one two left: no exact change, so the machine refunds Rs 30 and keeps the product.

EnumMap (episode 3) is a fast map whose keys are an enum, and it prints in the enum's order. new EnumMap<>(box) makes a copy, which is how the naive run doesn't damage the real box.

When greedy is not enough

Greedy can miss change that exists. Box: one 5 and three 2s, change Rs 6. Greedy takes the 5 first, leaves Rs 1, and can't pay it. But 2 + 2 + 2 = 6 works:

import java.util.*;
enum Coin { TEN(10), FIVE(5), TWO(2), ONE(1);  final int value;  Coin(int v) { value = v; } }   // biggest first
public class Main {
    static Map<Coin, Integer> naive(int change, Map<Coin, Integer> box) {   // greedy, never looks in the box
        Map<Coin, Integer> give = new EnumMap<>(Coin.class);
        for (Coin c : Coin.values())
            while (change >= c.value) {
                change -= c.value;  give.merge(c, 1, Integer::sum);  box.merge(c, -1, Integer::sum); }
        return give; }
    static Optional<Map<Coin, Integer>> makeChange(int change, Map<Coin, Integer> box) {
        Map<Coin, Integer> give = new EnumMap<>(Coin.class);
        for (Coin c : Coin.values()) {
            int n = Math.min(change / c.value, box.get(c));       // only coins we really have
            if (n > 0) { give.put(c, n);  change -= n * c.value; } }
        if (change != 0) return Optional.empty();                 // no exact change possible
        give.forEach((c, n) -> box.merge(c, -n, Integer::sum));   // take coins out only if it worked
        return Optional.of(give); }
    static void sell(int price, int paid, Map<Coin, Integer> box) {
        Optional<Map<Coin, Integer>> change = makeChange(paid - price, box);
        System.out.println("price " + price + ", paid " + paid + ": " + (change.isEmpty()
            ? "no exact change, REFUND Rs " + paid : "sold, change " + change.get() + ", box " + box)); }
    public static void main(String[] args) {
        Map<Coin, Integer> box = new EnumMap<>(Map.of(Coin.TEN, 1, Coin.FIVE, 0, Coin.TWO, 3, Coin.ONE, 1));
        Map<Coin, Integer> copy = new EnumMap<>(box);
        System.out.println(makeChange(6, new EnumMap<>(Map.of(Coin.TEN, 0, Coin.FIVE, 1, Coin.TWO, 3, Coin.ONE, 0))));
    }
}

Output:

Optional.empty

The expert fix tries every mix: dynamic programming (practice 3). For a coin set like ours (1, 2, 5, 10) with an unlimited supply of each, greedy always finds the fewest coins; it is the limited coins in a real box that break it.

8. Putting it together: select() in the right order

HasMoney.select with every piece in place:

Step Check If it fails
1 Does the product exist? "no such product", stay in HasMoney
2 Is it in stock? "SOLD OUT, pick another or cancel", stay
3 Is it paid for? "add Rs X", stay
4 Can we make exact change? REFUND everything → Idle
5 Dispensing: take from inventory, drop, pay change —
6 Idle —

Every check happens before anything leaves the machine. That is how it never owes anyone.

9. The class diagram

VendingMachine  (the context)
 ├─has──▶ State ── Idle · HasMoney · Dispensing   (insert / select / cancel)
 ├─has──▶ Inventory ── Product(code, name, price) → count
 ├─has──▶ coin box: EnumMap<Coin, Integer>
 └─takes─▶ Money ── Coin { ONE, TWO, FIVE, TEN } · Note { TEN, TWENTY, FIFTY, HUNDRED }
select(): exists? → in stock? → enough money? → exact change? → drop + change
anything fails before the drop → stay in HasMoney or REFUND

10. Interview follow-ups

Follow-up Answer
Restocking A Maintenance state entered with an operator PIN; buttons say "out of service" (practice 1)
Pay by UPI A payment strategy (episode 60): HasMoney accepts a PaymentMethod as well as coins
The customer walks away with money inside A timeout in HasMoney that refunds (practice 2)
Odd coin sets / limited coins Greedy can miss; use dynamic programming (practice 3)
A phone app and the keypad at once Make the context's button methods synchronized: one press at a time
Audit Log every sale and refund with an Observer (episode 35)
Notes as change A second box, EnumMap<Note, Integer>, tried before coins

11. Common mistakes

Mistake What you see Why Fix
State as a String busy, Rs 20 ignored then state = Idle, balance = 0 A typo compiles State pattern classes (or at least an enum)
if/else on the state in every method a new state breaks old methods Rules scattered One class per state
Leaving HasMoney on sold out the customer can't pick another product Wrong transition Stay in HasMoney; cancel refunds
No sold-out check in take() stock -1 Trusting every caller IllegalStateException: A1 is sold out
get() on an empty Optional NoSuchElementException: No value present The code didn't exist Check isEmpty() first
Greedy change ignoring the box box {TEN=0, FIVE=-1, TWO=3, ONE=1} Assumes infinite coins min(fit, in box)
Taking coins out before knowing the change works coins lost from the box on a refund Partial change Remove coins only on success
Dropping before checking change the machine owes the customer Wrong order Check change first, else REFUND
Money as double 0.1 + 0.2 prints 0.30000000000000004 Binary fractions Whole rupees (or paise) in an int

The double line is real Java: System.out.println(0.1 + 0.2); prints 0.30000000000000004. Keep money in whole units (rupees or paise) as integers.

Mini project: the complete machine

All of today's parts in one program: the State pattern, the inventory, Coin/Note behind Money, a coin box with greedy change over real coins, the five checks in the right order, refunds, and inserted coins added to the box for future change.

import java.util.*;

interface Money { int value(); }
enum Coin implements Money {
    TEN(10), FIVE(5), TWO(2), ONE(1);                                   // biggest first, for change
    private final int v;  Coin(int v) { this.v = v; }  public int value() { return v; }
}
enum Note implements Money {
    TEN(10), TWENTY(20), FIFTY(50), HUNDRED(100);
    private final int v;  Note(int v) { this.v = v; }  public int value() { return v; }
}
record Product(String code, String name, int price) {}

class Inventory {
    private final Map<String, Product> products = new HashMap<>();
    private final Map<String, Integer> count = new TreeMap<>();
    void add(Product p, int n) { products.put(p.code(), p); count.merge(p.code(), n, Integer::sum); }
    Optional<Product> find(String code) { return Optional.ofNullable(products.get(code)); }
    boolean soldOut(String code) { return count.getOrDefault(code, 0) == 0; }
    void take(String code) {
        if (soldOut(code)) throw new IllegalStateException(code + " is sold out");
        count.merge(code, -1, Integer::sum);
    }
    public String toString() { return "stock " + count; }
}

class CoinBox {                                                        // coins the machine can give as change
    private final Map<Coin, Integer> box = new EnumMap<>(Coin.class);
    CoinBox(Map<Coin, Integer> start) { box.putAll(start); }
    void add(Coin c) { box.merge(c, 1, Integer::sum); }
    Optional<Map<Coin, Integer>> makeChange(int change) {              // greedy over the coins really here
        Map<Coin, Integer> give = new EnumMap<>(Coin.class);
        for (Coin c : Coin.values()) {
            int n = Math.min(change / c.value(), box.getOrDefault(c, 0));
            if (n > 0) { give.put(c, n); change -= n * c.value(); }
        }
        return change == 0 ? Optional.of(give) : Optional.empty();
    }
    void pay(Map<Coin, Integer> give) { give.forEach((c, n) -> box.merge(c, -n, Integer::sum)); }
    public String toString() { return "box " + box; }
}

interface State { void insert(Money m); void select(String code); void cancel(); }

class VendingMachine {                                                 // the context
    final Inventory inventory = new Inventory();
    final CoinBox coins;
    final List<Money> inserted = new ArrayList<>();
    final State idle = new Idle(this), hasMoney = new HasMoney(this), dispensing = new Dispensing(this);
    State state = idle;
    VendingMachine(CoinBox coins) { this.coins = coins; }
    int balance() { return inserted.stream().mapToInt(Money::value).sum(); }
    void insert(Money m) { state.insert(m); }
    void select(String code) { state.select(code); }
    void cancel() { state.cancel(); }
    void say(String s) { System.out.println(state.getClass().getSimpleName() + ": " + s); }
    void refundAll() {
        say("REFUND " + inserted + " = Rs " + balance());
        inserted.clear(); state = idle;
    }
}

class Idle implements State {
    private final VendingMachine m;  Idle(VendingMachine m) { this.m = m; }
    public void insert(Money x) { m.inserted.add(x); m.state = m.hasMoney; m.say("balance Rs " + m.balance()); }
    public void select(String code) { m.say("insert money first"); }
    public void cancel() { m.say("nothing to refund"); }
}

class HasMoney implements State {
    private final VendingMachine m;  HasMoney(VendingMachine m) { this.m = m; }
    public void insert(Money x) { m.inserted.add(x); m.say("balance Rs " + m.balance()); }
    public void select(String code) {
        Optional<Product> found = m.inventory.find(code);
        if (found.isEmpty()) { m.say(code + ": no such product"); return; }           // 1. exists?
        Product p = found.get();
        if (m.inventory.soldOut(code)) { m.say(p.name() + ": SOLD OUT, pick another or cancel"); return; }   // 2. stock?
        if (m.balance() < p.price()) { m.say(p.name() + " costs Rs " + p.price() + ", add Rs " + (p.price() - m.balance())); return; }  // 3. paid?
        Optional<Map<Coin, Integer>> change = m.coins.makeChange(m.balance() - p.price());
        if (change.isEmpty()) { m.say("no exact change for Rs " + (m.balance() - p.price())); m.refundAll(); return; }  // 4. change?
        m.state = m.dispensing;
        ((Dispensing) m.dispensing).dispense(p, change.get());
    }
    public void cancel() { m.refundAll(); }
}

class Dispensing implements State {
    private final VendingMachine m;  Dispensing(VendingMachine m) { this.m = m; }
    void dispense(Product p, Map<Coin, Integer> change) {
        m.inventory.take(p.code());                                    // only now does anything leave the machine
        for (Money x : m.inserted) if (x instanceof Coin c) m.coins.add(c);   // inserted coins can be used as change later
        m.coins.pay(change);
        m.say("drop " + p.name() + ", change " + change + ", " + m.inventory + ", " + m.coins);
        m.inserted.clear(); m.state = m.idle;
    }
    public void insert(Money x) { m.say("please wait"); }
    public void select(String code) { m.say("please wait"); }
    public void cancel() { m.say("too late, it's dropping"); }
}

public class Main {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine(new CoinBox(Map.of(Coin.TEN, 1, Coin.FIVE, 1, Coin.TWO, 3, Coin.ONE, 1)));
        m.inventory.add(new Product("A1", "Chips", 20), 1);
        m.inventory.add(new Product("B2", "Juice", 35), 2);

        System.out.println("-- customer 1: juice with a fifty");
        m.select("B2");  m.insert(Note.FIFTY);  m.select("B2");
        System.out.println("-- customer 2: chips with a twenty, then again");
        m.insert(Note.TWENTY);  m.select("A1");  m.insert(Note.TWENTY);  m.select("A1");  m.cancel();
        System.out.println("-- customer 3: juice with a hundred (change Rs 65?)");
        m.insert(Note.HUNDRED);  m.select("C9");  m.select("B2");
        System.out.println("-- customer 4: juice with coins");
        m.insert(Coin.TEN);  m.insert(Coin.TEN);  m.insert(Coin.TEN);  m.select("B2");  m.insert(Coin.FIVE);  m.select("B2");
    }
}

Output:

-- customer 1: juice with a fifty
Idle: insert money first
HasMoney: balance Rs 50
Dispensing: drop Juice, change {TEN=1, FIVE=1}, stock {A1=1, B2=1}, box {TEN=0, FIVE=0, TWO=3, ONE=1}
-- customer 2: chips with a twenty, then again
HasMoney: balance Rs 20
Dispensing: drop Chips, change {}, stock {A1=0, B2=1}, box {TEN=0, FIVE=0, TWO=3, ONE=1}
HasMoney: balance Rs 20
HasMoney: Chips: SOLD OUT, pick another or cancel
HasMoney: REFUND [TWENTY] = Rs 20
-- customer 3: juice with a hundred (change Rs 65?)
HasMoney: balance Rs 100
HasMoney: C9: no such product
HasMoney: no exact change for Rs 65
HasMoney: REFUND [HUNDRED] = Rs 100
-- customer 4: juice with coins
HasMoney: balance Rs 10
HasMoney: balance Rs 20
HasMoney: balance Rs 30
HasMoney: Juice costs Rs 35, add Rs 5
HasMoney: balance Rs 35
Dispensing: drop Juice, change {}, stock {A1=0, B2=0}, box {TEN=3, FIVE=1, TWO=3, ONE=1}

Follow customer 1: the box gives the only ten and the only five as change. Customer 3 then needs Rs 65 in change, the box has only twos and a one, so the machine refunds the Rs 100 note and keeps the juice. Customer 4 pays in coins, which go into the box: now it holds three tens for the next customer's change.

Practice

1. Add a Maintenance state, entered from Idle with an operator PIN. In maintenance every button says "out of service" (and returns any money), the operator can restock, and done() returns to Idle.

Answer
interface State { void insert(int amount); void select(); void cancel(); }
class VendingMachine {
    static final String PIN = "4321";                                  // made-up operator PIN
    final State idle = new Idle(this), hasMoney = new HasMoney(this), maintenance = new Maintenance(this);
    State state = idle;  int balance = 0, chips = 0;  final int price = 20;
    void insert(int a) { state.insert(a); }   void select() { state.select(); }   void cancel() { state.cancel(); }
    void say(String s) { System.out.println(state.getClass().getSimpleName() + ": " + s); }
    void enterMaintenance(String pin) {
        if (state != idle) { say("finish the current sale first"); return; }
        if (!PIN.equals(pin)) { say("wrong PIN"); return; }
        state = maintenance;  say("out of service");
    }
}
class Idle implements State { final VendingMachine m;  Idle(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.state = m.hasMoney;  m.say("balance Rs " + m.balance); }
    public void select() { m.say("insert money first"); }
    public void cancel() { m.say("nothing to refund"); } }
class HasMoney implements State { final VendingMachine m;  HasMoney(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.say("balance Rs " + m.balance); }
    public void select() {
        if (m.chips == 0) { m.say("SOLD OUT, press cancel for a refund"); return; }
        if (m.balance < m.price) { m.say("add Rs " + (m.price - m.balance)); return; }
        m.chips--;  m.say("drop chips, change Rs " + (m.balance - m.price));  m.balance = 0;  m.state = m.idle; }
    public void cancel() { m.say("refund Rs " + m.balance);  m.balance = 0;  m.state = m.idle; } }
class Maintenance implements State { final VendingMachine m;  Maintenance(VendingMachine m) { this.m = m; }
    void restock(int n) { m.chips += n;  m.say("restocked, chips: " + m.chips); }
    void done() { m.state = m.idle;  m.say("back in service"); }
    public void insert(int a) { m.say("out of service, Rs " + a + " returned"); }
    public void select() { m.say("out of service"); }
    public void cancel() { m.say("out of service"); } }
public class Main {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine();
        m.insert(20);  m.select();  m.cancel();                        // sold out: refund
        m.enterMaintenance("1111");
        m.enterMaintenance("4321");
        m.insert(10);
        Maintenance mt = (Maintenance) m.maintenance;  mt.restock(5);  mt.done();
        m.insert(20);  m.select();
    }
}

Output:

HasMoney: balance Rs 20
HasMoney: SOLD OUT, press cancel for a refund
HasMoney: refund Rs 20
Idle: wrong PIN
Maintenance: out of service
Maintenance: out of service, Rs 10 returned
Maintenance: restocked, chips: 5
Idle: back in service
HasMoney: balance Rs 20
HasMoney: drop chips, change Rs 0

Only one new class (Maintenance) and one new method on the context: the other states didn't change. (To keep this short, HasMoney drops the chips itself here; in the full machine that's Dispensing's job.)

2. A customer inserts money and walks away. Add a timeout: after 3 ticks (standing in for 30 seconds) with no activity, HasMoney refunds and goes back to Idle. Inserting more money resets the timer.

Answer
interface State { void insert(int amount); void tick(); }
class VendingMachine {
    static final int TIMEOUT_TICKS = 3;                                // stands in for "30 seconds"
    final State idle = new Idle(this), hasMoney = new HasMoney(this);
    State state = idle;  int balance = 0, idleTicks = 0;
    void insert(int a) { state.insert(a); }   void tick() { state.tick(); }
    void say(String s) { System.out.println(state.getClass().getSimpleName() + ": " + s); }
}
class Idle implements State { final VendingMachine m;  Idle(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.idleTicks = 0;  m.state = m.hasMoney;  m.say("balance Rs " + m.balance); }
    public void tick() { } }
class HasMoney implements State { final VendingMachine m;  HasMoney(VendingMachine m) { this.m = m; }
    public void insert(int a) { m.balance += a;  m.idleTicks = 0;  m.say("balance Rs " + m.balance); }   // activity resets the timer
    public void tick() {
        m.idleTicks++;  m.say("waiting " + m.idleTicks + "/" + VendingMachine.TIMEOUT_TICKS);
        if (m.idleTicks >= VendingMachine.TIMEOUT_TICKS) { m.say("timeout, refund Rs " + m.balance);  m.balance = 0;  m.state = m.idle; }
    } }
public class Main {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine();
        m.insert(10);  m.tick();  m.tick();
        m.insert(10);  m.tick();  m.tick();  m.tick();
        m.tick();                                                      // already Idle: nothing happens
        System.out.println("balance now Rs " + m.balance);
    }
}

Output:

HasMoney: balance Rs 10
HasMoney: waiting 1/3
HasMoney: waiting 2/3
HasMoney: balance Rs 20
HasMoney: waiting 1/3
HasMoney: waiting 2/3
HasMoney: waiting 3/3
HasMoney: timeout, refund Rs 20
balance now Rs 0

The timer is driven by tick() instead of a real clock, so the test is instant and the same every run (episode 53).

3. Make change with the fewest coins, trying every mix, using at most the coins in the box. Show that Rs 6 from one 5 and three 2s works.

Answer

Dynamic programming (DP): solve small amounts first and build bigger answers from them. best[a] is the fewest-coins way to pay a with the coin types considered so far. For each coin type, try adding 1, 2, … up to the number in the box.

import java.util.*;
enum Coin { TEN(10), FIVE(5), TWO(2), ONE(1);  final int value;  Coin(int v) { value = v; } }
public class Main {
    // fewest coins for `change`, using at most box.get(c) of each coin: dynamic programming
    static Optional<Map<Coin, Integer>> makeChangeDP(int change, Map<Coin, Integer> box) {
        // best[a] = the fewest-coins way to pay a, using the coins considered so far (null = impossible)
        List<Map<Coin, Integer>> best = new ArrayList<>(Collections.nCopies(change + 1, null));
        best.set(0, new EnumMap<>(Coin.class));
        for (Coin c : Coin.values()) {
            int have = box.getOrDefault(c, 0);
            List<Map<Coin, Integer>> next = new ArrayList<>(best);
            for (int a = 0; a <= change; a++) {
                if (best.get(a) == null) continue;
                for (int k = 1; k <= have && a + k * c.value <= change; k++) {   // add k coins of type c
                    Map<Coin, Integer> option = new EnumMap<>(best.get(a));  option.put(c, k);
                    Map<Coin, Integer> old = next.get(a + k * c.value);
                    if (old == null || size(option) < size(old)) next.set(a + k * c.value, option);
                }
            }
            best = next;
        }
        return Optional.ofNullable(best.get(change));
    }
    static int size(Map<Coin, Integer> m) { return m.values().stream().mapToInt(Integer::intValue).sum(); }
    public static void main(String[] args) {
        Map<Coin, Integer> box = new EnumMap<>(Map.of(Coin.TEN, 0, Coin.FIVE, 1, Coin.TWO, 3, Coin.ONE, 0));
        System.out.println("change 6: " + makeChangeDP(6, box));
        System.out.println("change 7: " + makeChangeDP(7, box));
        System.out.println("change 9: " + makeChangeDP(9, box));
        System.out.println("change 4: " + makeChangeDP(4, box));
        System.out.println("change 1: " + makeChangeDP(1, box));
    }
}

Output:

change 6: Optional[{TWO=3}]
change 7: Optional[{FIVE=1, TWO=1}]
change 9: Optional[{FIVE=1, TWO=2}]
change 4: Optional[{TWO=2}]
change 1: Optional.empty

Greedy failed on 6; DP finds {TWO=3}. Rs 1 really is impossible with this box, so DP returns empty too, and the machine refunds.

4. (Thinking) Why does HasMoney stay in HasMoney when the product is sold out, instead of refunding at once?

Answer

The customer may want something else. Refunding at once forces them to insert all their coins again. Staying in HasMoney keeps the money and lets them pick another code or press cancel. A refund is the customer's choice, or the machine's last resort when it can't make change.

5. (Thinking) The machine has notes and coins. Why does the coin box hold only Coin, not Money?

Answer

Our requirement says change is given in coins only. Typing the box as EnumMap<Coin, Integer> makes the compiler enforce it: you can't put a Note into it. Types that match the rules turn rule-breaking into compile errors.

Quick quiz

Change needed: Rs 6. Box: TEN=0, FIVE=1, TWO=3, ONE=0. Our makeChange takes the biggest coin first, using only coins in the box. What does it return? (a) {FIVE=1, ONE=1} (b) {TWO=3} (c) Optional.empty, so a refund (d) {FIVE=1}

Answer

(c) Optional.empty, so a refund. Greedy takes the five first, leaving Rs 1; no two fits into 1 and there's no one, so it returns empty (section 7 shows the real Optional.empty). But 2 + 2 + 2 = 6 was possible: greedy missed it. The DP in practice 3 finds {TWO=3}.

Interview questions

  1. Which design pattern fits a vending machine, and why? The State pattern: the same buttons do different things in Idle, HasMoney and Dispensing. One class per state keeps each state's rules together; the machine (context) delegates.
  2. What are the states? Idle (no money), HasMoney (money in, choosing), Dispensing (dropping). Often also Maintenance / OutOfService.
  3. Why not an enum and a switch? For a few states with tiny behaviour, an enum state machine is fine (episode 37). As behaviour grows, switches spread into every method; the State pattern keeps one state's behaviour in one class and makes new states additive.
  4. How do you handle sold-out products? Check in select and stay in HasMoney; check again in Inventory.take so stock can't go negative.
  5. How do you compute change? Greedy, biggest coin first, limited by the coins in the box; remove coins only if the whole change works; else refund. For limited coin counts, greedy can fail: use DP.
  6. When do you check change: before or after dropping? Before. Every check (exists, stock, paid, change) comes before anything leaves the machine.
  7. How is a refund done? Return exactly the money inserted (keep the list of inserted coins/notes), clear the balance, go to Idle.
  8. Why not store money as double? Binary fractions: 0.1 + 0.2 is 0.30000000000000004. Use integers in the smallest unit.
  9. How would you add restocking? A Maintenance state with an operator PIN; no other state changes.
  10. Is it thread-safe? A single keypad is one user at a time; with an app and a keypad, make the context's button methods synchronized so presses happen one at a time.

Glossary

Term Meaning, with an example
Vending machine (LLD problem) A classic machine-coding problem: products, money, states, change and refunds
Vending machine requirements What it must do: accept money, choose by code, drop if in stock and paid, exact change, refund on cancel
Requirement Something the system must do, agreed before coding
Entity A thing in the problem with its own data and rules: Product, Inventory
Product What you buy: Product("A1", "Chips", 20)
Inventory The products inside and their counts: {A1=1, B2=3}
Stock How many of a product are left
Sold-out handling Refusing a product whose count is 0, staying in HasMoney, and never letting stock go below 0
Coin and Note enums enum Coin { ONE, TWO, FIVE, TEN }, enum Note { TEN, TWENTY, FIFTY, HUNDRED }, each with a value
Money interface interface Money { int value(); }, implemented by both enums
Balance The money inserted so far in this sale
State What the machine is doing right now: Idle, HasMoney, Dispensing
State pattern Each state is its own class behind one interface; the context delegates to the current state
State interface The methods every state implements: insert, select, cancel
Concrete state One class per state: Idle, HasMoney, Dispensing
Context The object that holds the current state and delegates to it: VendingMachine
Delegate Hand a job to another object: insert(a) { state.insert(a); }
Transition A change of state: m.state = m.hasMoney
Idle No money inserted; waiting
HasMoney Money inserted; the customer is choosing
Dispensing The product is dropping; buttons wait
Maintenance An operator state for restocking; buttons say "out of service"
Change Paid minus price, given back in coins
Change calculation Working out which coins to give as change
Greedy algorithm Always take the biggest coin that fits; fast, but can miss with limited coins
Dynamic programming Solving small cases first and building bigger answers from them; finds change greedy misses
Coin box The coins the machine holds for change: EnumMap<Coin, Integer>
Refund Giving back all the money inserted, when the customer cancels or the sale can't complete
Cancel The coin-return button; each state decides what it means
Timeout Doing something automatically after a time with no activity: refund after 30 s
Defensive programming Checking again where the data lives, even if callers should have checked
Optional A box that may be empty: find("C9") returns Optional.empty
EnumMap A fast map with enum keys, printed in the enum's order
TreeMap A map that keeps its keys sorted
Record A short class that just holds values: record Product(String code, String name, int price)
Cast Telling Java an object is a more specific type: (Dispensing) m.dispensing
IllegalStateException Java's exception for "can't do that now": A1 is sold out
State vs Strategy Both hide behaviour behind an interface; strategies are chosen by the caller, states switch themselves
Typo-safe Using enums or classes instead of strings so the compiler catches misspellings

Summary

  • Requirements: accept coins and notes, choose by code, drop only if in stock and paid, exact change from the box, cancel → refund. Golden rule: never keep money without giving the product.
  • A String state with a typo ("Idle" vs "IDLE") stuck the machine: busy, Rs 20 ignored.
  • The State pattern: Idle, HasMoney, Dispensing behind one State interface; VendingMachine is the context and delegates. New states (Maintenance) are new classes, not edits everywhere.
  • Product is a record; Inventory maps codes to products and counts; sold out keeps the machine in HasMoney, and take refuses to go below 0 (A1 is sold out).
  • Coin and Note are enums behind Money.
  • Change: greedy over the coins really in the box, removed only on success; no exact change → refund before the drop. Naive greedy produced FIVE=-1; with limited coins, greedy can miss (6 = 2 + 2 + 2), and dynamic programming finds it.
  • select checks exists → stock → paid → change, and only then drops.

Next episode: Design an ATM: cards, PINs, accounts, ATM states, withdrawals and the note dispenser.