ATM: the state machine, cash dispensing and failure recovery

The model is ready for failure: devices behind interfaces, a transaction log, an idempotency key. This lesson puts it to work. It draws the session state machine, writes the cash-dispensing plan that refuses rather than part-pays, and then answers the question every interviewer asks on this problem — what happens when the account was debited and the notes jam.

The ATM state machine

The happy path is five states in a line. The design is in the other six.

The states

Ten states, and four of them exist only for failure. That ratio is the point of this problem.

Two rules that shape every transition

Every state where a human must act has a timeout. A customer who walks away mid-session cannot leave the machine occupied. Thirty seconds is a reasonable figure to state; the exact number is configuration.

A card left in the slot is retained. After ejecting, if the card is not taken within about thirty seconds, it is pulled back in. This protects the customer from the next person taking their card, and it is a real behaviour worth knowing.

Why State classes here and a switch in the elevator

The elevator dispatch loop used an exhaustive switch and argued for it. Here, use state classes. The difference is worth stating out loud, because inconsistency looks like carelessness unless you name the reason:

"In the elevator I used a switch, because it was six states and one method. Here there are ten states and six events, which is sixty cases, and about half of them are refusals with different messages. That is exactly where the State pattern pays: each state class answers all six events, and the compiler makes sure I haven't forgotten one."

Sixty cases in one method is the threshold. Naming the threshold is better than having a rule.

Cash dispensing, in code

Given ₹3,700 and cassettes of ₹500, ₹200, and ₹100 notes, which notes come out? And when should the machine refuse?

The naive version and its two bugs

1// WRONG2public void dispense(Money amount) {3    int remaining = amount.toRupees();4    int fiveHundreds = remaining / 500;  remaining %= 500;5    int twoHundreds  = remaining / 200;  remaining %= 200;6    int hundreds     = remaining / 100;  remaining %= 100;7    dispenser.dispense(Map.of(N500, fiveHundreds, N200, twoHundreds, N100, hundreds));8}

Bug one: it ignores what the machine actually holds. If the ₹500 cassette is empty, this asks for seven notes that do not exist.

Bug two: it dispenses before checking the remainder. ₹3,750 leaves ₹50 unaccounted for, and the machine has already released ₹3,700. The check must come first, always.

Chain of Responsibility

Each denomination handles what it can and passes the rest along. It suits this problem because the handlers are naturally ordered, each does the same kind of work, and adding a ₹2,000 note is a new link rather than an edit.

1public abstract class NoteHandler {2    private NoteHandler next;3    protected abstract Denomination denomination();45    public NoteHandler setNext(NoteHandler next) { this.next = next; return next; }67    /** Adds this denomination's contribution to plan, returns what is still owed. */8    public int handle(int amountOwed, CashInventory inventory, Map<Denomination, Integer> plan) {9        int noteValue = denomination().value();10        int wanted = amountOwed / noteValue;11        int available = inventory.countOf(denomination());12        int used = Math.min(wanted, available);1314        if (used > 0) {15            plan.put(denomination(), used);16            amountOwed -= used * noteValue;17        }18        return (next == null) ? amountOwed : next.handle(amountOwed, inventory, plan);19    }20}2122public class FiveHundredHandler extends NoteHandler {23    protected Denomination denomination() { return Denomination.N500; }24}25// TwoHundredHandler, HundredHandler identical but for the denomination.

The dispenser then plans first and acts second:

1public class CashDispenserService {2    private final NoteHandler chain;      // 500 -> 200 -> 10034    public Map<Denomination, Integer> planFor(Money amount, CashInventory inventory) {5        Map<Denomination, Integer> plan = new LinkedHashMap<>();6        int stillOwed = chain.handle(amount.toRupees(), inventory, plan);7        if (stillOwed != 0) {8            throw new CannotDispenseAmountException(amount, stillOwed);   // refuse, do not part-pay9        }10        return plan;11    }12}

planFor never touches hardware. It is a pure function of the amount and the inventory, so it can be tested exhaustively — which matters because this is the code that decides whether money leaves the machine.

Where greedy fails, and being honest about it

Greedy — take as many of the largest note as possible — is not always right when stock is limited. Concrete case, worth having ready:

The machine holds one ₹500 note and plenty of ₹200 notes. A customer asks for ₹600. Greedy takes the ₹500, leaves ₹100 owed, and there are no ₹100 notes. It refuses. But ₹600 = three ₹200 notes. The money was there.

For ordinary denomination sets with healthy stock, greedy is right nearly always, and it is what real machines mostly do — which is why they refuse "odd" amounts and ask you to try a multiple of ₹500.

The complete solution is dynamic programming over the amount, bounded by the note counts:

// Sketch: dp[a] = fewest notes to make amount a with the notes in stock; reconstruct the plan.// Amounts are in hundreds, so the table is amount/100 entries wide — tiny for ATM limits.

The recommendation: ship greedy, and say the rest. "Greedy with stock limits covers standard denominations and is what I'd ship. It can refuse an amount that is technically makeable — one ₹500 and many ₹200s, asked for ₹600 — and if that mattered, this is a bounded coin-change problem solved with dynamic programming over the amount, which is small enough here to be free. I'd ship greedy and log refusals to see whether it ever bites."

That is a complete answer: the simple solution, the case where it fails, the correct solution, and a way to find out whether it matters.

Extensions

1. The dispense-failure question, which is always asked

"The account was debited and the notes jammed. What happens?"

Answer in four parts, and be specific:

Part one — order the operations to shrink the window. Where the bank supports it, use a hold rather than a debit:

1HoldReference hold = bankService.holdFunds(account, amount, transaction.getId());  // reversible2Map<Denomination, Integer> plan = dispenserService.planFor(amount, inventory);     // may refuse3inventory.reserve(plan);4dispenser.dispense(plan);                                                          // physical5bankService.captureHold(hold);                                                     // now it is real

The window where money is committed but notes are undelivered shrinks to the gap between the motor finishing and the capture call — and the reserve/hold shape is the same one used for seats in Section 5 and stock in Section 9.

Part two — log every step durably, before doing it. The TransactionLog from Finding the objects records the intention before each irreversible action. After a power cut, startup reads the log and finds entries with an intention and no completion.

Part three — reverse on failure.

1} catch (DispenseFailedException e) {2    transactionLog.append(new LogEntry(txId, DISPENSE_FAILED, notesActuallyDispensed(e)));3    bankService.reverse(txId);                      // idempotent, keyed by transaction id4    inventory.release(plan);5    atm.changeState(atm.errorState());              // will still eject the card6    screen.display("Transaction cancelled. Your account has not been charged.");7}

Part four — reconcile what the machine cannot know. A partial dispense — three notes out, two jammed — cannot be resolved by the machine, because the motor's count and physical reality have diverged. The honest answer:

"A partial dispense is not resolvable in software. The machine logs what it believes it dispensed and moves to out-of-service. A technician counts the cassettes and the reject bin, and the difference reconciles the customer's account. That is what real machines do, and I'd rather have a design that goes out of service and preserves the evidence than one that guesses."

Preferring an honest out-of-service to a guess is the right instinct, and saying it as a design principle rather than a shrug is what makes it score.

2. Idempotency, and the concurrency question

Raise this yourself — it is where this problem ends.

Every call to the bank carries the transaction id as an idempotency key. If the network times out, the ATM does not know whether the debit happened. It retries with the same key, and the bank either performs the operation or returns the result of the original — but never debits twice.

1public interface BankService {2    DebitResult debit(String accountId, Money amount, String idempotencyKey);3    void reverse(String idempotencyKey);4}

The concurrency here is not two customers at one machine — there is one card slot. It is three other things, and naming them is the senior answer:

• The machine and the bank act on the same account concurrently. The same account may be used at another ATM or in an app at the same instant, so the daily-limit check and the debit must be one atomic operation at the bank, not two calls from the ATM. An ATM that checks the limit and then debits has a race it cannot fix locally.
• A retry races its own original request. Handled by the idempotency key.
• Device events arrive on different threads. The card sensor, the keypad, and the dispenser's completion signal are separate interrupts. Same answer as the vending machine extensions: one event queue, one thread draining it, so state transitions are serialised.

3. Daily withdrawal limits

Limits belong at the bank, not at the ATM, and the reason is the first bullet above: an ATM cannot enforce a daily limit across other machines and channels. The ATM sends the request; the bank approves or declines with a reason. Any local limit check is a courtesy that saves a network round trip, never the enforcement point.

4. Multi-currency

Cassettes become currency-specific, and the plan-and-refuse logic runs per currency. The interesting part is the exchange: the customer's account is in one currency and the notes are in another, so the rate must be quoted, shown, and locked for the transaction — a quote object with an expiry, which is the same freeze-the-price argument as the movie booking extensions.

5. Cash replenishment

A cassette is a physically swappable unit, so replenishment is a swap, not a top-up: the old cassette is removed with its remaining count, a full one is inserted, and both counts are logged against the technician's identity. Model Cassette as its own object with an id and a count, and CashInventory as the set of currently loaded cassettes. That makes reconciliation possible — the machine's belief and the cassette's physical count can be compared, which is exactly what part four above needs.