Two machines, one idea: behaviour depends on state
A vending machine and an ATM are both small, physical machines that react to a sequence of user actions: insert, select, cancel; insert card, enter PIN, withdraw. The same action means different things at different moments. Pressing "select" before inserting money should be refused; pressing it after inserting enough money should dispense. Entering a PIN before inserting a card is meaningless.
That is why both are classic interview problems for the State pattern, where each state is an object that decides how to handle each action and which state comes next. The ATM adds a second classic pattern, the Chain of Responsibility, for splitting a withdrawal amount across note denominations. Both problems also hide an algorithm that candidates often get wrong: making change, or paying out notes, with a limited supply.
What interviewers probe:
- Can you draw the state diagram first, and only then write classes?
- Do your states reject invalid actions cleanly instead of scattering
if (state == ...)checks? - Do you handle the money edge cases: refunds on cancel, sold-out items, and "cannot make change"?
- For the ATM: the PIN retry limit, the order of debit and dispense, and what happens if the dispenser fails after the account was debited.
- Concurrency: one machine has one user at a time, but the bank account behind an ATM is shared by every ATM and the mobile app.
This lesson designs both, explains the patterns and algorithms with worked examples, and runs both machines in one Java program whose real output is included. Read Behavioural patterns for a refresher on State and Chain of Responsibility.
Part 1: the vending machine
Problem statement
Design a coin-operated vending machine. It has slots with products, each with a price and a quantity. A user inserts coins, selects a slot, and receives the product and any change. The user can cancel before buying and get their coins back. The operator restocks products.
Clarifying questions and assumed requirements
| Question | Assumed answer | Effect on the design |
|---|---|---|
| Coins or notes? | Coins of Rs 1, 2, 5, 10 and 20 | Coin enum |
| Insert first or select first? | Insert first, then select | Idle refuses select |
| Can the user add more coins after a "not enough" message? | Yes | Stay in the has-money state |
| Does the machine give change? | Yes, from its own coin box, which has limited coins | Change-making with limited supply |
| What if change cannot be made? | Refuse the sale; user can add coins or cancel | No partial sale |
| What if a slot is empty? | Tell the user; let them choose another or cancel | Slot quantity check |
| What if every slot is empty? | Machine goes out of service and returns any coin inserted | Out-of-stock state |
| One user at a time? | Yes physically; a phone app could also act, so make operations atomic | synchronized methods |
Functional requirements: insert coins, select a product, dispense product and change, cancel with a full refund, refuse sold-out products, refuse sales when change cannot be made, go out of stock, restock.
Non-functional requirements: money is never lost or created (coins in equal coins out plus coins kept); invalid actions in any state are handled gracefully; new states (maintenance, card payment) can be added without rewriting existing ones.
Core use cases
- Insert Rs 10, select Water (Rs 20): told to insert Rs 10 more.
- Insert two Rs 5 coins, select Water: dispensed, no change.
- Insert Rs 20, select Chips (Rs 15): dispensed with Rs 5 change.
- Select a sold-out product: told to choose another; cancel returns the coins.
- Insert Rs 20 for Coffee (Rs 12) when Rs 8 change is impossible: refused; insert Rs 2 more and get Rs 10 change.
- The last product is sold: machine goes out of stock until restocked.
State diagram
insert coin
+-------+ ---------------> +-----------+ insert coin (stay)
| IDLE | | HAS_MONEY | <-------------+
+-------+ <--------------- +-----------+ --------------+
^ ^ cancel: | select: not enough, sold out,
| | refund coins | or change impossible (stay)
| | |
| | | select: enough money and
| | | change can be made
| | more stock left v
| +------------------ +------------+
| | DISPENSING |
| restock +------------+
| | that was the last item
| v
| +--------------+
+-----------------------| OUT_OF_STOCK | insert coin: returned
+--------------+
Every state handles every action. In most states most actions are invalid, and the right response is a message, not an exception. Java's default interface methods let each state override only the actions it accepts:
interface VendingState {
default void insert(VendingMachine m, Coin c) { m.say("cannot insert coins now"); }
default void select(VendingMachine m, String code) { m.say("cannot select now"); }
default void cancel(VendingMachine m) { m.say("nothing to cancel"); }
default void dispense(VendingMachine m) { m.say("nothing to dispense"); }
}
Entities and relationships
+------------------+ 1 1 +-----------+ 1 * +------+ 1 1 +---------+
| VendingMachine |-------| Inventory |-------| Slot |-------| Product |
|------------------| +-----------+ +------+ +---------+
| state | code, quantity
| escrow: coins | 1 1 +---------+
| insert/select/ |-------| CoinBox | coins owned, makeChange()
| cancel/restock | +---------+
+------------------+
| current state
v
VendingState <|-- IdleState, HasMoneyState, DispensingState, OutOfStockState
| Class | Responsibility |
|---|---|
Coin | Denominations and values |
Product, Slot, Inventory | What is for sale, where, and how many |
CoinBox | Coins the machine owns; plans change |
VendingState and four states | Behaviour per state and transitions |
VendingMachine | Context: holds the current state, the escrow, and helpers states call |
Escrow: coins that are not yet the machine's
A key detail: coins the user inserts are held in an escrow, a temporary holding area, not added to the coin box straight away. On cancel, the machine returns exactly the coins the user inserted. Only when a sale completes are escrow coins moved into the coin box. Real machines physically do the same. If you add inserted coins directly to the box, a cancel must "make change" for the refund, which can fail.
Change-making with a limited supply
When a sale needs change, the machine must choose coins from its box. The famous greedy method takes as many of the largest coin as possible, then the next largest, and so on. For an unlimited supply of standard coin systems such as Indian rupee coins, greedy gives the fewest coins. But a vending machine has a limited number of each coin, and then greedy can fail even when change is possible.
Worked example. The box holds one Rs 5 coin and three Rs 2 coins, and no Rs 1 coins. Change needed: Rs 6.
Greedy:
Rs 20, 10: none
Rs 5: take 1, remaining 1
Rs 2: 1 / 2 = 0
Rs 1: none in the box
remaining 1 -> FAILS
Backtracking:
try 1 x Rs 5, remaining 1 -> no way to make 1 -> back off
try 0 x Rs 5, remaining 6 -> 3 x Rs 2 = 6 -> SUCCESS {TWO=3}
The code's makeChange is a backtracking search: for each coin from largest to smallest, it tries the largest usable count first and steps down if the rest cannot be completed. It still prefers large coins, so it usually returns few coins, and it finds a solution whenever one exists. The search space is tiny for five denominations and small counts. Larger systems would use dynamic programming over the amount (a bounded coin change), as in the DSA practice problems.
Some amounts are simply impossible. With the same box, Rs 8 needs either a Rs 5 plus Rs 3 (impossible without Rs 1 coins) or four Rs 2 coins (only three available), so makeChange(8) fails. The program prints all three results.
Reserve change before dispensing
HasMoneyState.select checks, in order:
- Is the slot sold out?
- Has enough money been inserted?
- Can change be made? Plan it using the box plus the escrow, because the user's own coins can be part of their change.
Only if all three pass does the machine move to DISPENSING. Checking change before dispensing matters: dispensing first and then discovering no change is possible would leave the machine owing the user money. If change is impossible, the machine stays in HAS_MONEY, so the user can add a coin that makes it possible, or cancel.
Common mistake
Dispensing the product and then computing change. If change turns out to be impossible, you have already given away the product and cannot refund the full amount either. Plan change first; dispense only when the whole transaction can complete.
Why the State pattern beats a switch here
A switch-based design has a method per action, each with a switch over four states: sixteen cases, mostly "not allowed". Adding a MAINTENANCE state means editing all four methods. With the State pattern, a MaintenanceState class overrides only what it accepts, and existing states change only where they transition into it. Each state class is also small enough to test alone.
States share no per-machine data, so the machine creates one instance of each and switches between them. Data such as the escrow and chosen slot lives on the machine.
Part 2: the ATM
Problem statement
Design an ATM (automated teller machine). A customer inserts a card, enters a PIN, and performs transactions: balance inquiry, cash withdrawal and deposit. The ATM dispenses notes from cassettes of different denominations. After three wrong PINs, the card is retained. The ATM talks to the bank, which holds accounts.
Clarifying questions and assumed requirements
| Question | Assumed answer | Effect on the design |
|---|---|---|
| Note denominations? | Rs 500, 200 and 100 | Three cassettes |
| Withdrawal rules? | Multiples of Rs 100, at most Rs 20,000 per transaction | Validation |
| PIN retry limit? | 3, then retain the card | Counter and a retained state |
| Transactions? | Balance, withdrawal, deposit; transfer as an extension | Transaction interface |
| Several transactions per session? | Yes, until the card is ejected | Session stays authenticated |
| Where is the balance? | At the bank, shared with other ATMs and apps | Bank-side locking |
| Dispenser failure after debit? | Reverse the debit | Compensation |
Functional requirements: card and PIN authentication with a retry limit; balance inquiry; withdrawal that dispenses an exact combination of available notes and debits the account; deposit; eject card.
Non-functional requirements: money safety (never debit without dispensing, never dispense without debiting); correctness when the same account is used from two places at once; clear rejection of invalid actions in each state.
ATM state machine
insertCard (known) enterPin (correct)
+------+ -------------> +---------------+ -------------> +---------------+
| IDLE | | CARD_INSERTED | | AUTHENTICATED |
+------+ <------------- +---------------+ +---------------+
^ ^ eject | wrong PIN, tries left (stay) | perform(tx)
| | | | (stay)
| | | 3rd wrong PIN |
| | v |
| | +---------------+ |
| +------------| CARD_RETAINED | |
| eject: +---------------+ |
| card kept |
+--------------------------------------------------------+
eject: card returned
The ATM has fewer interactions per state than the vending machine, so the code uses an enum plus a require(state) guard at the top of each operation. This is a legitimate, lighter form of a state machine. If the interviewer asks for the full State pattern, each enum value becomes a class exactly as in the vending machine. Being able to say when the lighter version is enough is itself a good signal.
Entities and relationships
+-------+ uses +------+ 1 * +---------+
| Atm |------->| Bank |-------| Account | balance, pin (hash in reality)
|-------| +------+ +---------+ debit()/credit() synchronized
| state |
| card | performs +-------------+
| tries |------------>| Transaction |<|-- BalanceInquiry, Withdrawal, Deposit
+-------+ +-------------+
| 1
v 1
+---------------+ head of chain
| CashDispenser |-------------> Cassette(500) -> Cassette(200) -> Cassette(100)
+---------------+ (each is a NoteHandler)
| Class | Responsibility |
|---|---|
Atm | Session state machine: card, PIN tries, current account |
Bank, Account | Verifies card and PIN; holds balances; debit and credit are atomic |
Transaction and three records | One class per transaction type: the Command pattern, an action packaged as an object |
NoteHandler, Cassette | Chain of responsibility: each handler pays what it can in its note |
CashDispenser | Builds the chain, plans and dispenses notes |
Chain of Responsibility for the cash dispenser
The Chain of Responsibility pattern passes a request along a chain of handlers; each handler does its part (or nothing) and passes the rest to the next. For a cash dispenser, each handler is a cassette:
- The Rs 500 handler pays as many Rs 500 notes as it can without exceeding the amount or its stock.
- It passes the remaining amount to the Rs 200 handler.
- The Rs 200 handler does the same and passes the rest to the Rs 100 handler.
- If anything remains at the end of the chain, the amount cannot be dispensed.
Adding a Rs 2,000 cassette or removing the Rs 200 one means relinking the chain; no handler's code changes.
Worked example 1. Cassettes hold 500 × 2, 200 × 5, 100 × 10 (total Rs 3,000). Withdraw Rs 1,800.
500 handler: min(1800 / 500, 2) = min(3, 2) = 2 notes -> Rs 1000, rest 800
200 handler: min(800 / 200, 5) = 4 notes -> Rs 800, rest 0
100 handler: not reached
Plan: {500 x 2, 200 x 4}. Cassettes after: 500 x 0, 200 x 1, 100 x 10
Worked example 2. Now withdraw Rs 600 from the remaining cassettes.
500 handler: 0 notes left rest 600
200 handler: min(600 / 200, 1) = 1 note rest 400
100 handler: min(400 / 100, 10) = 4 notes rest 0
Plan: {200 x 1, 100 x 4}
Worked example 3: the chain's limitation. A different machine has 500 × 1, 200 × 3 and no Rs 100 notes. Withdraw Rs 600.
500 handler: 1 note, rest 100
200 handler: 100 / 200 = 0 notes, rest 100
100 handler: none, rest 100 -> chain FAILS
But 200 x 3 = 600 would have worked.
This is the same flaw as greedy change-making: each handler decides locally, with no backtracking. Real ATMs reduce the problem by stocking plenty of small notes and by showing which amounts are available. In an interview, point out the limitation and offer fixes: let a handler retry with one fewer note when the rest of the chain fails (backtracking along the chain), or plan with a bounded coin-change algorithm outside the chain. The demo prints no plan for this case, which is honest behaviour: the ATM refuses rather than guessing.
Plan, then debit, then dispense
The order of steps in a withdrawal decides whether money can be lost:
1. Validate amount (multiple of 100, within limit)
2. Plan notes (dry run, cassettes untouched) -> refuse if impossible
3. Debit the account atomically -> refuse if insufficient
4. Physically dispense the planned notes
5. If dispensing fails: credit the account back (compensation)
Planning first avoids debiting money for an amount the machine cannot pay. Debiting before dispensing means that if two ATMs race on one account, the bank decides who wins before any notes move. And if hardware fails after the debit, a compensating transaction credits the money back. Real systems also log every step so a reconciliation process can match what the cassette counters say against what the bank recorded.
Interview tip
Say the order out loud: "plan, debit, dispense, compensate on failure". Then answer the follow-up before it comes: "If the ATM loses power between debit and dispense, the bank sees a debit without a dispense confirmation, and reconciliation reverses it." That is what interviewers want to hear about money safety.
PIN handling
The ATM counts wrong PINs in the session; on the third, it moves to CARD_RETAINED and refuses every transaction until the session ends, keeping the card. In reality, the PIN is never compared in plain text: it is encrypted in the keypad and verified in a hardware security module at the bank, and the retry count is stored at the bank so that moving to another ATM does not reset it. The demo's pinMatches is a stand-in for that, and the code comments say so.
Complete Java implementation
Both machines are in one file. Save as VendingAtmDemo.java, compile with javac VendingAtmDemo.java and run java VendingAtmDemo. Java 17 or later is needed for records.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
// =====================================================================
// VENDING MACHINE
// =====================================================================
enum Coin {
ONE(1), TWO(2), FIVE(5), TEN(10), TWENTY(20);
final int value;
Coin(int value) { this.value = value; }
}
record Product(String name, int price) {}
final class Slot {
final String code; final Product product; int quantity;
Slot(String code, Product product, int quantity) { this.code = code; this.product = product; this.quantity = quantity; }
}
final class Inventory {
private final Map<String, Slot> slots = new LinkedHashMap<>();
void add(String code, Product p, int qty) { slots.put(code, new Slot(code, p, qty)); }
Slot slot(String code) {
Slot s = slots.get(code);
if (s == null) throw new IllegalArgumentException("no slot " + code);
return s;
}
boolean allEmpty() { return slots.values().stream().allMatch(s -> s.quantity == 0); }
}
/** Coins the machine owns. Change-making searches with backtracking because coin counts are limited. */
final class CoinBox {
private final EnumMap<Coin, Integer> counts = new EnumMap<>(Coin.class);
CoinBox() { for (Coin c : Coin.values()) counts.put(c, 0); }
void add(Coin c, int n) { counts.merge(c, n, Integer::sum); }
void addAll(Map<Coin, Integer> coins) { coins.forEach(this::add); }
void removeAll(Map<Coin, Integer> coins) { coins.forEach((c, n) -> counts.merge(c, -n, Integer::sum)); }
/** Fewest-coins-first search: try as many of the largest coin as possible, back off if stuck. */
Optional<Map<Coin, Integer>> makeChange(int amount) {
Coin[] desc = Coin.values().clone();
Arrays.sort(desc, (a, b) -> b.value - a.value);
Map<Coin, Integer> plan = new EnumMap<>(Coin.class);
return search(desc, 0, amount, plan) ? Optional.of(plan) : Optional.empty();
}
private boolean search(Coin[] desc, int i, int remaining, Map<Coin, Integer> plan) {
if (remaining == 0) return true;
if (i == desc.length) return false;
Coin c = desc[i];
for (int n = Math.min(remaining / c.value, counts.get(c)); n >= 0; n--) {
if (n > 0) plan.put(c, n); else plan.remove(c);
if (search(desc, i + 1, remaining - n * c.value, plan)) return true;
}
plan.remove(c);
return false;
}
/** Plain greedy without backtracking, kept only to show where it fails. */
Optional<Map<Coin, Integer>> greedyChange(int amount) {
Map<Coin, Integer> plan = new EnumMap<>(Coin.class);
Coin[] desc = Coin.values().clone();
Arrays.sort(desc, (a, b) -> b.value - a.value);
for (Coin c : desc) {
int n = Math.min(amount / c.value, counts.get(c));
if (n > 0) { plan.put(c, n); amount -= n * c.value; }
}
return amount == 0 ? Optional.of(plan) : Optional.empty();
}
}
// ---------- State pattern ----------
interface VendingState {
default void insert(VendingMachine m, Coin c) { m.say("cannot insert coins now"); }
default void select(VendingMachine m, String code) { m.say("cannot select now"); }
default void cancel(VendingMachine m) { m.say("nothing to cancel"); }
default void dispense(VendingMachine m) { m.say("nothing to dispense"); }
String name();
}
final class IdleState implements VendingState {
public String name() { return "IDLE"; }
public void insert(VendingMachine m, Coin c) { m.escrowAdd(c); m.setState(m.hasMoney); }
public void select(VendingMachine m, String code) { m.say("insert money first"); }
}
final class HasMoneyState implements VendingState {
public String name() { return "HAS_MONEY"; }
public void insert(VendingMachine m, Coin c) { m.escrowAdd(c); }
public void cancel(VendingMachine m) { m.refundEscrow("cancelled"); m.setState(m.idle); }
public void select(VendingMachine m, String code) {
Slot s = m.inventory().slot(code);
if (s.quantity == 0) { m.say(s.product.name() + " is sold out, choose another or cancel"); return; }
int paid = m.escrowTotal();
if (paid < s.product.price()) { m.say("insert Rs " + (s.product.price() - paid) + " more"); return; }
if (!m.reserveChange(paid - s.product.price())) {
m.say("cannot make change of Rs " + (paid - s.product.price()) + ", use exact money");
return; // stay in HAS_MONEY: user may add coins or cancel
}
m.chosen(s);
m.setState(m.dispensing);
m.state().dispense(m);
}
}
final class DispensingState implements VendingState {
public String name() { return "DISPENSING"; }
public void dispense(VendingMachine m) {
m.completeSale();
m.setState(m.inventory().allEmpty() ? m.outOfStock : m.idle);
}
}
final class OutOfStockState implements VendingState {
public String name() { return "OUT_OF_STOCK"; }
public void insert(VendingMachine m, Coin c) { m.say("machine is empty, returning Rs " + c.value); }
}
final class VendingMachine {
final VendingState idle = new IdleState(), hasMoney = new HasMoneyState(),
dispensing = new DispensingState(), outOfStock = new OutOfStockState();
private VendingState state = idle;
private final Inventory inventory;
private final CoinBox box;
private final EnumMap<Coin, Integer> escrow = new EnumMap<>(Coin.class); // inserted, not yet ours
private Map<Coin, Integer> pendingChange = Map.of();
private Slot chosen;
VendingMachine(Inventory inventory, CoinBox box) {
this.inventory = inventory; this.box = box;
if (inventory.allEmpty()) state = outOfStock;
}
// Public operations: synchronized, because a phone app and the keypad could act at once.
synchronized void insert(Coin c) { state.insert(this, c); }
synchronized void select(String code) { state.select(this, code); }
synchronized void cancel() { state.cancel(this); }
synchronized void restock(String code, int qty) {
inventory.slot(code).quantity += qty;
if (state == outOfStock) setState(idle);
}
// Helpers used by states.
void setState(VendingState s) { state = s; }
VendingState state() { return state; }
Inventory inventory() { return inventory; }
void say(String msg) { System.out.println(" [" + state.name() + "] " + msg); }
void escrowAdd(Coin c) { escrow.merge(c, 1, Integer::sum); say("inserted Rs " + c.value + ", total Rs " + escrowTotal()); }
int escrowTotal() { return escrow.entrySet().stream().mapToInt(e -> e.getKey().value * e.getValue()).sum(); }
void chosen(Slot s) { chosen = s; }
/** Inserted coins can be used for change, so plan change as if the sale went through. */
boolean reserveChange(int change) {
box.addAll(escrow);
Optional<Map<Coin, Integer>> plan = box.makeChange(change);
box.removeAll(escrow);
plan.ifPresent(p -> pendingChange = p);
return plan.isPresent();
}
void completeSale() {
box.addAll(escrow);
box.removeAll(pendingChange);
chosen.quantity--;
say("dispensed " + chosen.product.name() + (pendingChange.isEmpty() ? "" : ", change " + pendingChange));
escrow.clear();
pendingChange = Map.of();
chosen = null;
}
void refundEscrow(String why) { say(why + ", returning " + new EnumMap<>(escrow)); escrow.clear(); }
}
// =====================================================================
// ATM
// =====================================================================
enum Note { FIVE_HUNDRED(500), TWO_HUNDRED(200), ONE_HUNDRED(100);
final int value; Note(int v) { value = v; } }
/** Chain of responsibility: each handler pays what it can in its note and passes the rest on. */
abstract class NoteHandler {
private NoteHandler next;
NoteHandler linkTo(NoteHandler next) { this.next = next; return next; }
/** Builds a plan without touching the cassettes. Returns the amount nobody could pay. */
int plan(int amount, Map<Note, Integer> out) {
int n = Math.min(amount / note().value, available());
if (n > 0) out.put(note(), n);
int rest = amount - n * note().value;
return (rest == 0 || next == null) ? rest : next.plan(rest, out);
}
abstract Note note();
abstract int available();
}
final class Cassette extends NoteHandler {
private final Note note; private int count;
Cassette(Note note, int count) { this.note = note; this.count = count; }
Note note() { return note; }
int available() { return count; }
void take(int n) { if (n > count) throw new IllegalStateException("cassette short"); count -= n; }
void load(int n) { count += n; }
}
final class CashDispenser {
private final Map<Note, Cassette> cassettes = new EnumMap<>(Note.class);
private final NoteHandler head;
CashDispenser(int fiveHundreds, int twoHundreds, int hundreds) {
Cassette c500 = new Cassette(Note.FIVE_HUNDRED, fiveHundreds), c200 = new Cassette(Note.TWO_HUNDRED, twoHundreds),
c100 = new Cassette(Note.ONE_HUNDRED, hundreds);
cassettes.put(Note.FIVE_HUNDRED, c500); cassettes.put(Note.TWO_HUNDRED, c200); cassettes.put(Note.ONE_HUNDRED, c100);
c500.linkTo(c200).linkTo(c100);
head = c500;
}
Optional<Map<Note, Integer>> plan(int amount) {
Map<Note, Integer> out = new EnumMap<>(Note.class);
return head.plan(amount, out) == 0 ? Optional.of(out) : Optional.empty();
}
void dispense(Map<Note, Integer> plan) { plan.forEach((n, k) -> cassettes.get(n).take(k)); }
int total() { return cassettes.values().stream().mapToInt(c -> c.note().value * c.available()).sum(); }
String stock() {
StringBuilder sb = new StringBuilder();
cassettes.forEach((n, c) -> sb.append(n.value).append('x').append(c.available()).append(' '));
return sb.toString().trim();
}
}
// ---------- Bank side (shared by every ATM, so it must be thread-safe) ----------
final class Account {
final String number; private long balance; private final String pin;
Account(String number, long balance, String pin) { this.number = number; this.balance = balance; this.pin = pin; }
synchronized boolean debit(long amount) { if (amount > balance) return false; balance -= amount; return true; }
synchronized void credit(long amount) { balance += amount; }
synchronized long balance() { return balance; }
boolean pinMatches(String p) { return pin.equals(p); } // real systems compare a salted hash inside an HSM
}
final class Bank {
private final Map<String, Account> byCard = new ConcurrentHashMap<>();
void issue(String card, Account a) { byCard.put(card, a); }
Optional<Account> verify(String card, String pin) {
Account a = byCard.get(card);
return a != null && a.pinMatches(pin) ? Optional.of(a) : Optional.empty();
}
boolean known(String card) { return byCard.containsKey(card); }
}
// ---------- Transactions (command objects) ----------
interface Transaction { String execute(Account acct, CashDispenser cash); }
record BalanceInquiry() implements Transaction {
public String execute(Account a, CashDispenser c) { return "balance Rs " + a.balance(); }
}
record Deposit(int amount) implements Transaction {
public String execute(Account a, CashDispenser c) {
if (amount <= 0) return "invalid amount";
a.credit(amount);
return "deposited Rs " + amount + ", balance Rs " + a.balance();
}
}
record Withdrawal(int amount) implements Transaction {
public String execute(Account a, CashDispenser cash) {
if (amount <= 0 || amount % 100 != 0) return "enter a multiple of Rs 100";
if (amount > 20_000) return "per-transaction limit is Rs 20000";
Optional<Map<Note, Integer>> plan = cash.plan(amount); // 1. can the machine pay it?
if (plan.isEmpty()) return "cannot dispense Rs " + amount + " with notes available";
if (!a.debit(amount)) return "insufficient funds"; // 2. debit atomically
try {
cash.dispense(plan.get()); // 3. move notes
} catch (RuntimeException hardwareFault) {
a.credit(amount); // compensate
return "dispense failed, account not charged";
}
return "dispensed " + plan.get() + ", balance Rs " + a.balance();
}
}
// ---------- ATM state machine ----------
enum AtmState { IDLE, CARD_INSERTED, AUTHENTICATED, CARD_RETAINED }
final class Atm {
static final int MAX_PIN_TRIES = 3;
private final Bank bank; private final CashDispenser cash;
private AtmState state = AtmState.IDLE;
private String card; private Account account; private int pinTries;
Atm(Bank bank, CashDispenser cash) { this.bank = bank; this.cash = cash; }
private void require(AtmState s) {
if (state != s) throw new IllegalStateException("not allowed in state " + state);
}
String insertCard(String cardNumber) {
require(AtmState.IDLE);
if (!bank.known(cardNumber)) return "card not recognised, returned";
card = cardNumber; pinTries = 0; state = AtmState.CARD_INSERTED;
return "enter PIN";
}
String enterPin(String pin) {
require(AtmState.CARD_INSERTED);
Optional<Account> a = bank.verify(card, pin);
if (a.isPresent()) { account = a.get(); state = AtmState.AUTHENTICATED; return "PIN ok"; }
if (++pinTries >= MAX_PIN_TRIES) { state = AtmState.CARD_RETAINED; return "wrong PIN 3 times, card retained"; }
int left = MAX_PIN_TRIES - pinTries;
return "wrong PIN, " + left + (left == 1 ? " try" : " tries") + " left";
}
String perform(Transaction t) {
require(AtmState.AUTHENTICATED);
return t.execute(account, cash);
}
String eject() {
if (state == AtmState.CARD_RETAINED) { reset(); return "session over, card kept for the bank"; }
if (state == AtmState.IDLE) return "no card";
reset();
return "card returned";
}
private void reset() { state = AtmState.IDLE; card = null; account = null; pinTries = 0; }
AtmState state() { return state; }
CashDispenser cash() { return cash; }
}
public class VendingAtmDemo {
public static void main(String[] args) throws Exception {
System.out.println("=== VENDING MACHINE ===");
System.out.println("1. Change-making with limited coins (one 5, three 2s, no 1s)");
CoinBox sample = new CoinBox();
sample.add(Coin.FIVE, 1); sample.add(Coin.TWO, 3);
System.out.println(" Rs 6 greedy: " + sample.greedyChange(6).map(Object::toString).orElse("FAILS"));
System.out.println(" Rs 6 backtracking: " + sample.makeChange(6).map(Object::toString).orElse("FAILS"));
System.out.println(" Rs 8 backtracking: " + sample.makeChange(8).map(Object::toString).orElse("FAILS"));
Inventory inv = new Inventory();
inv.add("A1", new Product("Water", 20), 2);
inv.add("B1", new Product("Chips", 15), 1);
inv.add("C1", new Product("Coffee", 12), 1);
CoinBox box = new CoinBox();
box.add(Coin.FIVE, 1); box.add(Coin.TWO, 3);
VendingMachine vm = new VendingMachine(inv, box);
System.out.println("2. Buy Water (Rs 20) with Rs 10 + 5 + 5, then Chips (Rs 15) with Rs 20");
vm.select("A1");
vm.insert(Coin.TEN); vm.select("A1");
vm.insert(Coin.FIVE); vm.insert(Coin.FIVE); vm.select("A1");
vm.insert(Coin.TWENTY); vm.select("B1");
System.out.println("3. Sold-out slot, then cancel");
vm.insert(Coin.TWENTY); vm.select("B1"); vm.cancel();
System.out.println("4. Coffee (Rs 12) with Rs 20: Rs 8 change is impossible, so add Rs 2");
vm.insert(Coin.TWENTY); vm.select("C1");
vm.insert(Coin.TWO); vm.select("C1");
System.out.println("5. Last Water empties the machine");
vm.insert(Coin.TWENTY); vm.select("A1");
vm.insert(Coin.TEN);
vm.restock("B1", 5);
System.out.println(" after restock: " + vm.state().name());
System.out.println();
System.out.println("=== ATM ===");
Bank bank = new Bank();
Account shared = new Account("ACC-1", 10_000, "4321");
bank.issue("CARD-1", shared);
Atm atm = new Atm(bank, new CashDispenser(2, 5, 10));
System.out.println("cassettes: " + atm.cash().stock() + " (Rs " + atm.cash().total() + ")");
System.out.println("6. PIN flow and transactions");
System.out.println(" " + atm.insertCard("CARD-1"));
System.out.println(" " + atm.enterPin("1111"));
System.out.println(" " + atm.enterPin("4321"));
System.out.println(" " + atm.perform(new BalanceInquiry()));
System.out.println(" " + atm.perform(new Withdrawal(1800)));
System.out.println(" cassettes: " + atm.cash().stock());
System.out.println(" " + atm.perform(new Withdrawal(600)));
System.out.println(" chain limitation: 500x1 200x3 100x0 asked for 600 -> "
+ new CashDispenser(1, 3, 0).plan(600).map(Object::toString).orElse("no plan"));
System.out.println(" " + atm.perform(new Withdrawal(250)));
System.out.println(" " + atm.perform(new Deposit(500)));
System.out.println(" " + atm.eject());
System.out.println("7. Three wrong PINs");
atm.insertCard("CARD-1");
for (String p : List.of("0000", "1234", "9999")) System.out.println(" " + atm.enterPin(p));
try { atm.perform(new BalanceInquiry()); } catch (IllegalStateException e) { System.out.println(" " + e.getMessage()); }
System.out.println(" " + atm.eject());
System.out.println("8. Two ATMs withdraw Rs 7000 from the same Rs " + shared.balance() + " account at once");
Atm a1 = new Atm(bank, new CashDispenser(20, 0, 0)), a2 = new Atm(bank, new CashDispenser(20, 0, 0));
for (Atm a : List.of(a1, a2)) { a.insertCard("CARD-1"); a.enterPin("4321"); }
ExecutorService pool = Executors.newFixedThreadPool(2);
CountDownLatch go = new CountDownLatch(1);
Future<String> r1 = pool.submit(() -> { go.await(); return a1.perform(new Withdrawal(7000)); });
Future<String> r2 = pool.submit(() -> { go.await(); return a2.perform(new Withdrawal(7000)); });
go.countDown();
List<String> results = new ArrayList<>(List.of(r1.get(), r2.get()));
Collections.sort(results);
results.forEach(r -> System.out.println(" " + r));
System.out.println(" final balance Rs " + shared.balance());
pool.shutdown();
}
}
Real output
This is the actual output from Temurin JDK 21:
=== VENDING MACHINE ===
1. Change-making with limited coins (one 5, three 2s, no 1s)
Rs 6 greedy: FAILS
Rs 6 backtracking: {TWO=3}
Rs 8 backtracking: FAILS
2. Buy Water (Rs 20) with Rs 10 + 5 + 5, then Chips (Rs 15) with Rs 20
[IDLE] insert money first
[IDLE] inserted Rs 10, total Rs 10
[HAS_MONEY] insert Rs 10 more
[HAS_MONEY] inserted Rs 5, total Rs 15
[HAS_MONEY] inserted Rs 5, total Rs 20
[DISPENSING] dispensed Water
[IDLE] inserted Rs 20, total Rs 20
[DISPENSING] dispensed Chips, change {FIVE=1}
3. Sold-out slot, then cancel
[IDLE] inserted Rs 20, total Rs 20
[HAS_MONEY] Chips is sold out, choose another or cancel
[HAS_MONEY] cancelled, returning {TWENTY=1}
4. Coffee (Rs 12) with Rs 20: Rs 8 change is impossible, so add Rs 2
[IDLE] inserted Rs 20, total Rs 20
[HAS_MONEY] cannot make change of Rs 8, use exact money
[HAS_MONEY] inserted Rs 2, total Rs 22
[DISPENSING] dispensed Coffee, change {TEN=1}
5. Last Water empties the machine
[IDLE] inserted Rs 20, total Rs 20
[DISPENSING] dispensed Water
[OUT_OF_STOCK] machine is empty, returning Rs 10
after restock: IDLE
=== ATM ===
cassettes: 500x2 200x5 100x10 (Rs 3000)
6. PIN flow and transactions
enter PIN
wrong PIN, 2 tries left
PIN ok
balance Rs 10000
dispensed {FIVE_HUNDRED=2, TWO_HUNDRED=4}, balance Rs 8200
cassettes: 500x0 200x1 100x10
dispensed {TWO_HUNDRED=1, ONE_HUNDRED=4}, balance Rs 7600
chain limitation: 500x1 200x3 100x0 asked for 600 -> no plan
enter a multiple of Rs 100
deposited Rs 500, balance Rs 8100
card returned
7. Three wrong PINs
wrong PIN, 2 tries left
wrong PIN, 1 try left
wrong PIN 3 times, card retained
not allowed in state CARD_RETAINED
session over, card kept for the bank
8. Two ATMs withdraw Rs 7000 from the same Rs 8100 account at once
dispensed {FIVE_HUNDRED=14}, balance Rs 1100
insufficient funds
final balance Rs 1100
Checking the vending machine output
Track the coin box through the run. It starts with one Rs 5 and three Rs 2 coins.
Water: escrow 10 + 5 + 5 = 20, change 0
box: 10x1, 5x3, 2x3
Chips: escrow 20, change 5 -> one Rs 5 coin
box: 20x1, 10x1, 5x2, 2x3
Sold-out Chips, cancel: escrow returned, box unchanged
Coffee with 20: change 8
5 + 2 = 7 (short 1), 5 + 5 = 10 (too much),
2 + 2 + 2 = 6 (short 2), so impossible
Add Rs 2: total 22, change 10 -> one Rs 10 coin
The output matches each step: Water with no change, Chips with {FIVE=1}, the sold-out message and a refund of exactly the Rs 20 coin, the refusal for Rs 8 change, and Coffee with {TEN=1} after the extra coin. Selling the last Water empties every slot, so a coin inserted next is returned, and restocking brings the machine back to IDLE.
Checking the ATM output
- Balance Rs 10,000. Withdrawing Rs 1,800 gives 500 × 2 and 200 × 4 (worked example 1), balance Rs 8,200.
- Rs 600 gives 200 × 1 and 100 × 4 (worked example 2), balance Rs 7,600.
- The separate dispenser with 500 × 1 and 200 × 3 finds no plan for Rs 600 (worked example 3).
- Rs 250 is rejected for not being a multiple of 100; a Rs 500 deposit brings the balance to Rs 8,100.
- Three wrong PINs retain the card; any transaction is then refused.
- Two ATMs each try to withdraw Rs 7,000 from the Rs 8,100 account at the same moment. Exactly one succeeds (14 notes of Rs 500), the other gets "insufficient funds", and the final balance is Rs 1,100.
Concurrency considerations
The vending machine
A vending machine has one keypad, but modern machines also accept app or QR payments, and an operator might restock while a customer is buying. Each public method (insert, select, cancel, restock) is synchronized on the machine, so one action completes, including its state transition, before the next begins. The lock is held only for in-memory work. Slow hardware actions (motors, coin hoppers) would be triggered after the state change, or the dispensing state would wait for a hardware callback before returning to idle.
Coarse locking is right here: there is one machine, few actions per second, and correctness matters far more than throughput.
The ATM and the shared account
Each ATM serves one customer, so ATM session state needs no locks. The account, however, is shared: a joint account can be used at two ATMs at once, plus a mobile app. The withdrawal's debit is a check-then-act (if balance >= amount then balance -= amount), so it must be atomic. Account.debit is synchronized on the account, which is the right granularity: different accounts never contend.
Without that lock, both ATMs could read Rs 8,100, both decide Rs 7,000 is affordable, and both dispense: Rs 14,000 paid from an Rs 8,100 account. The demo's last section starts both withdrawals at the same instant with a latch; exactly one succeeds every time.
In a real bank, the account lives in a database, and the debit is a single conditional update such as UPDATE account SET balance = balance - 7000 WHERE id = ? AND balance >= 7000, checking that one row changed. See Transactions and ACID and Concurrency control.
Idempotency
Networks between ATM and bank fail. If the ATM sends "debit Rs 7,000" and the reply is lost, it must not simply resend and risk a double debit. Each request carries a unique transaction id; the bank records processed ids and returns the original result for a repeat. This is idempotency: performing the same request twice has the same effect as once.
Extensions interviewers ask, and how the design absorbs them
Vending machine
- Card or UPI payment. A
PaymentMethodstrategy: coins go through escrow; card payments authorise the exact price. A newAwaitingPaymentStatewaits for the authorisation callback. - Maintenance mode. A
MaintenanceStatethat refuses customers and accepts restock and coin collection. - Select first, then pay. Reorder the states:
ProductSelectedStateshows the price and accepts coins until enough is inserted. - Low-change alert. An observer on the coin box notifies the operator when a denomination runs low, and the display shows "exact change only".
- Multiple items in one transaction. Keep a cart in the machine; change is planned once for the total.
ATM
- Fund transfer and PIN change. New
Transactionclasses. The ATM's state machine does not change. - Mini statement. Another transaction that reads recent entries from the bank.
- Daily withdrawal limit. Stored at the bank per card; checked inside the same atomic debit.
- Cassette low or empty. The dispenser reports available amounts so the screen offers only possible values; an observer alerts operations.
- Session timeout. A timer that ejects the card after inactivity: a transition from any state to
IDLEorCARD_RETAINED. - Deposit with note counting. A deposit module validates and counts notes, then credits after the customer confirms.
- Better note plans. Replace pure greedy handlers with a planner that backtracks or prefers mixing denominations so that small notes are not exhausted.
Common mistakes
- Boolean flags like
hasMoneyandisDispensinginstead of explicit states. - Exceptions for normal invalid actions, such as pressing select in idle; a message is enough.
- Adding inserted coins straight to the coin box, making cancellation refunds unreliable.
- Greedy change-making with limited coins without noticing it can fail when a solution exists.
- Dispensing before confirming change can be made.
- Debiting after dispensing, or dispensing without a plan, in the ATM.
- No compensation if dispensing fails after a debit.
- Locking the whole bank for one account's withdrawal, or not locking at all.
- Keeping the PIN retry count only in the ATM, so moving to the next ATM resets it.
- Ignoring idempotency for requests between ATM and bank.
Interview questions
Q1. Why use the State pattern for a vending machine?
Each action's meaning depends on the current state, and some actions are invalid in some states. The State pattern puts each state's behaviour in its own class and makes transitions explicit, so adding a state such as maintenance needs a new class rather than edits to every switch statement.
Q2. What states does a vending machine need?
At least idle, has-money, dispensing and out-of-stock. Some designs add product-selected (select before pay) or maintenance. The exact set depends on the clarified flow, which is why you agree on it before coding.
Q3. How does the machine make change with limited coins?
It searches from the largest coin down, using as many as possible, and backtracks if the remainder cannot be completed. Plain greedy is wrong with limited supply: with one Rs 5 and three Rs 2 coins, greedy fails for Rs 6 while three Rs 2 coins work.
Q4. What happens if change cannot be made?
The sale is refused before dispensing, and the machine stays in the has-money state so the user can insert a coin that makes change possible or cancel for a full refund. The machine can also display "exact change only" when its box is low.
Q5. Why keep inserted coins in escrow?
So a cancel returns exactly the coins the user inserted, which always succeeds. Coins enter the machine's box only when a sale completes. It also lets the user's own coins be used as part of their change.
Q6. How does the chain of responsibility dispense cash?
Each cassette is a handler that pays as many of its notes as fit, without exceeding stock, and passes the remainder to the next handler. If anything remains at the end of the chain, the amount cannot be paid. New denominations are added by relinking the chain.
Q7. What is the weakness of the chain approach, and how would you fix it?
Each handler decides greedily, so it can miss a valid combination: with 500 × 1 and 200 × 3, it fails to pay Rs 600 though three Rs 200 notes would work. Fix it with backtracking (retry with one fewer large note when the rest fails) or a bounded coin-change planner.
Q8. In what order should a withdrawal debit and dispense?
Plan the notes first, then debit the account atomically, then dispense, and credit back if dispensing fails. This ensures the machine never pays out without a successful debit and the customer is never charged for an amount the machine could not pay.
Q9. Two ATMs withdraw from the same account at once. What prevents overdrawing?
The bank's debit is an atomic check-and-subtract: a lock on the account object, or a conditional database update that only succeeds if the balance is still sufficient. Exactly one of two competing withdrawals that together exceed the balance succeeds.
Q10. How do you handle three wrong PINs?
Count failures and move to a card-retained state on the third, refusing all transactions and keeping the card when the session ends. In production, the bank stores the counter, so the limit holds across ATMs.
Q11. Which pattern fits the different transaction types?
The Command pattern: each transaction type is an object with an execute method. The ATM runs any transaction the same way, and adding a new type such as fund transfer needs no change to the ATM.
Q12. What if the network to the bank fails after a debit request?
The ATM retries with the same transaction id; the bank recognises the id and returns the original result without debiting again. If the outcome is still unknown, the ATM does not dispense, and reconciliation later reverses any orphaned debit.
Q13. When is an enum-based state machine acceptable instead of the State pattern?
When states have few, simple behaviours and are unlikely to grow, a guard like require(state) at the top of each operation is clear and short. When states have rich, different behaviour per action, or new states are expected, separate state classes scale better.
Key takeaways
- Draw the state diagram first; then each state becomes a class (or an enum value for simple machines).
- Use default methods so each state overrides only the actions it accepts; invalid actions get a message.
- Keep inserted coins in escrow; refund exactly what was inserted on cancel.
- Plan change with backtracking before dispensing; greedy can fail with limited coins.
- A cash dispenser is a chain of responsibility over cassettes; know its greedy limitation and a fix.
- Withdraw in the order plan, debit, dispense, compensate on failure; make the debit atomic at the bank.
- Lock at the right level: the whole vending machine, but only the individual account at the bank.
Next lesson
Continue with LLD interview practice.