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).
- Accept coins and notes; show the balance (how much has been put in so far).
- Choose a product by its code, like
A1. - Drop the product only if it is in stock and fully paid.
- Give exact change, from the coins really inside the machine.
- 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 ifchain: 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:
VendingMachinemakes 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 asHasMoney:Idle.insertswitched the state before printing.((Dispensing) m.dispensing).dispense()is a cast:dispense()isn't part of theStateinterface (no button calls it), so we tell Java that thisStatereally is aDispensing.- 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:
- In
HasMoney.select: if the count is 0, refuse and stay in HasMoney, so the customer can pick another product or cancel. - 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:
- Use only coins really in the box: take
min(how many fit, how many we have)of each. - Remove coins from the box only if the whole change worked.
- 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
- 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.
- What are the states? Idle (no money), HasMoney (money in, choosing), Dispensing (dropping). Often also Maintenance / OutOfService.
- 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.
- How do you handle sold-out products? Check in
selectand stay in HasMoney; check again inInventory.takeso stock can't go negative. - 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.
- When do you check change: before or after dropping? Before. Every check (exists, stock, paid, change) comes before anything leaves the machine.
- How is a refund done? Return exactly the money inserted (keep the list of inserted coins/notes), clear the balance, go to Idle.
- Why not store money as
double? Binary fractions:0.1 + 0.2is0.30000000000000004. Use integers in the smallest unit. - How would you add restocking? A Maintenance state with an operator PIN; no other state changes.
- 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
synchronizedso 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,Dispensingbehind oneStateinterface;VendingMachineis 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
takerefuses 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. selectchecks exists → stock → paid → change, and only then drops.
Next episode: Design an ATM: cards, PINs, accounts, ATM states, withdrawals and the note dispenser.