Design an ATM

What this design is really about

An ATM is a small state machine wrapped around money. A customer inserts a card, authenticates with a PIN, and then drives a session in which exactly one transaction happens at a time. The interesting engineering is not the class list — it is two things that must never go wrong: (1) the machine must always know which step of the session it is in, and (2) it must never debit an account for cash it cannot physically hand out. The model below is organized around those two invariants.

Core responsibilities

• Session lifecycle: idle → card inserted → authenticated → transaction selected → ejected. Illegal jumps (e.g. selecting a withdrawal before authenticating) must be impossible, not merely discouraged.
• Cash dispensing: given an amount and a finite inventory of bills, decide whether the amount can be made and, if so, which bills to release — checking feasibility before any account is debited.
• Transaction semantics: each transaction (balance inquiry, deposit cash, deposit check, withdraw, transfer) returns a status, and a non-success status must roll the session back cleanly.

Modeling the session: State pattern — and when not to use it

The session moves through a fixed set of stages, and what the machine accepts depends entirely on the current stage. Inserting a card means nothing once you are already authenticated; selecting a withdrawal means nothing before you are. This is the textbook shape for the State pattern: give each stage its own object, let each object implement only the transitions that are legal from it, and have it return the next state.

abstract class ATMState {
    ATMState insertCard(ATM atm, Card card)      { return reject(); }
    ATMState enterPin(ATM atm, int pin)          { return reject(); }
    ATMState selectTransaction(ATM atm, Transaction txn) { return reject(); }
    ATMState cancel(ATM atm)                      { atm.ejectCard(); return new IdleState(); }
    private ATMState reject() { /* show "invalid operation" */ return this; }
}

class AuthenticatedState extends ATMState {
    @Override
    ATMState selectTransaction(ATM atm, Transaction txn) {
        TransactionStatus result = txn.execute(atm);
        if (result == TransactionStatus.SUCCESS) {
            atm.printReceipt(txn);
            atm.ejectCard();
            return new IdleState();
        }
        // FAILURE / undispensable / insufficient funds:
        // do NOT print a success receipt, do NOT silently eject.
        atm.showError(result);          // surface the reason
        return this;                    // stay authenticated; let the user retry or cancel
    }
}

The key correctness point lives in selectTransaction: it captures the result and branches on it. Only a SUCCESS prints a receipt and ejects the card. A FAILURE (insufficient funds, or an amount the dispenser cannot make) keeps the session alive so the customer can try a different amount or cancel — and crucially it never prints a receipt for money that was not dispensed. An earlier draft ignored result and unconditionally printed and ejected; that is the single most important bug to avoid on this page, because it directly violates the "check feasibility before debiting, and surface failures" invariant.

When NOT to reach for State

State earns its keep here because there are five-plus stages, several transition rules, and behavior that genuinely differs per stage. That justification does not generalize. If you only have two or three trivial stages with no per-stage behavior — for example a toy machine that is just LOCKED vs UNLOCKED — a plain enum plus a switch is simpler, has less indirection, and is easier to read. The State pattern trades a switch for a set of classes; that trade only pays off once the number of states and the divergence in behavior are large enough that the switch would otherwise sprawl across the codebase. Reaching for State on two states is over-engineering. The honest rule: use a switch until the conditionals start duplicating across methods, then promote to State.

The interesting algorithm: making change from a finite till

When a withdrawal is approved, the dispenser must turn an amount into actual bills drawn from a finite inventory. This is the change-making problem, and the right algorithm depends entirely on the denomination set and the inventory — so the first job is to know which case you are in.

Selection guidance (the part that actually matters)

The denomination set used throughout this page is {50, 20, 10, 5}. That set is canonical, and greedy is provably optimal on it. I verified this exhaustively with a DP over every amount from 0 to 500: there are zero amounts where greedy uses more bills than the optimum, and zero amounts where greedy fails to find a split that exists. So for this exact problem, with ample inventory, greedy is not just "good enough" — it is the correct, optimal choice, and reaching for DP would be over-engineering.

Greedy is not universally correct, and it is worth knowing exactly when it breaks so you can recognize the non-canonical case in an interview:

• Non-canonical set: with denominations {25, 20, 10} and a target of 40, greedy takes 25, then is stuck (15 cannot be made), so it reports failure — yet 20 + 20 is a valid two-bill answer. Here greedy fails while a solution exists. This is the real "greedy can fail" case; it does not occur on {50,20,10,5}.
• Finite inventory: even on a canonical set, if the till is short on the smaller denominations greedy needs to finish, its largest-first grab can strand the remainder. Withdrawing $60 from a till holding 1×$50, 3×$20, 0×$10, 0×$5: greedy takes the $50, leaving $10 — but there are no $10 or $5 bills, so it dead-ends and reports failure, while inventory-aware backtracking simply declines the $50 and pays 3×$20. This is where the naive and inventory-aware strategies genuinely diverge. (Note that a greedy which merely falls through to smaller bills would not have failed on $80 from 1×$50, 1×$10, 6×$5 — it would take $50 + $10 + 4×$5 without trouble; the real trap is a large bill that leaves an unmakeable remainder, as with the $50 above.)

So the dispenser's real algorithm is feasibility-first and inventory-aware: canDispense(amount) must run the bounded search and confirm a valid bill combination before the account is debited; only then does dispenseCash release exactly those bills. On the canonical set with ample stock that bounded search degenerates to plain greedy.

A trace that actually demonstrates the divergence

The point of a trace is to show naive greedy failing where a valid combination exists, and inventory-aware search succeeding on the same input. The amount is $60 and the till holds 1×$50, 3×$20, 0×$10, 0×$5 — a finite-inventory case, since the denomination set itself is canonical.

The two columns genuinely differ and the thesis is demonstrated: a valid combination exists (3×$20), inventory-aware search finds it by declining the $50, and a strictly largest-first greedy that commits to the $50 strands the final $10 with no small bills to cover it. Note the cause is the finite till, not the denomination set — on an unlimited {50,20,10,5} till, greedy would have produced $50 + $10 and there would be no divergence at all. That is exactly why the selection table above gates greedy on "ample inventory," and why a real dispenser runs the bounded, backtracking search rather than a one-pass greedy.

And a correct rejection, for contrast: withdrawing $30 from a till of 1×$50, 0×$20, 0×$10, 4×$5. The maximum usable here is 4×$5 = $20 < $30 — no valid combination exists, so every algorithm must reject. That is the right answer, not a greedy failure; it is included only to show that canDispense returning false is sometimes simply correct.

A note on the skeleton code's conventions

The provided skeleton uses body-less method signatures on classes (for example public boolean makeTransaction(Transaction transaction); on Customer) and getters such as getAccountId. It is worth being precise about what is and isn't a real defect here, because an earlier draft overstated this:

• Not a real bug — skeleton style. Body-less signatures and getter conventions are normal skeleton/pseudocode shorthand: the intent is "these methods exist; bodies omitted for brevity." In real Java they'd compile once the bodies are added (on a concrete class) or once the type is an interface/abstract method. Framing them as "won't compile" is a strawman, not a finding.
• An actual smell — the return type. BalanceInquiry stores private int accountId; but exposes public double getAccountId();. Returning a double for a value held as int compiles only by silent widening, and an account identifier should never be a floating-point value (precision and formatting both bite you). This one is worth fixing: make it public int getAccountId();.

The distinction matters for interview judgment: call out the genuine type defect, but don't manufacture a compile error out of ordinary skeleton notation.

Where the real consistency lives: the account the ATM does not own

Every lock and feasibility check on this page lives inside one machine's process. That is the honest scope of an LLD answer — and it is worth saying out loud where it stops, because the staff-level follow-up lands exactly on the seam. The genuinely hard invariant is not local: the money in the cassette is physical and this-machine, but the account balance lives on a bank backend (the issuer, reached through a switch) over a network the ATM does not control. Two failure modes a strong interviewer will push on:

• The same account, debited from two places at once (this ATM plus a second ATM, or a concurrent online transfer). The synchronized monitors here guard this machine's cassette inventory — they do nothing about the account. Serialising a balance is the backend's job (a conditional debit / row lock at the account of record), never something an ATM process can enforce.
• Cash moves but the message is lost. The debit is recorded but the network drops before the dispense confirms — or notes are physically dispensed but the confirmation back to the switch never arrives. Handing out cash is irreversible: it is the point of no return, and no rollback exists for banknotes already in a customer's hand.

The defended ordering (vs the naive alternative). Debit-then-dispense risks charging a customer who then gets no cash (the dispenser jams, or the machine loses power between the two steps). Dispense-then-debit risks handing out money you can never collect. Neither one-step order is safe, so real ATM networks use a hold-and-settle protocol: authorize a hold on the account first, dispense, then confirm the completion. If the confirmation is uncertain the transaction is left in-doubt and resolved by the daily reconciliation / settlement file — the switch reverses an authorized-but-undispensed hold, or re-posts a dispensed-but-unconfirmed debit. A per-transaction idempotency key makes every confirm, reverse, or retry safe to replay exactly once.

The honest limit, stated plainly: the class model on this page is the correct single-machine core — session state and inventory-aware dispensing on one box. The money-safety of an ATM is a distributed-transaction problem that lives in the switch and the nightly settlement, deliberately outside the LLD class list. Knowing precisely which invariant the synchronized keyword can and cannot buy you — cassette inventory yes, account balance no — is the line between a candidate who has memorised the State pattern and one who has run money in production.

Citation

Adapted and corrected from the "Design an ATM" object-oriented design problem (Grokking the Object-Oriented Design Interview / Educative), with the original problem statement, requirements, actors, and skeleton class model retained. The greedy-optimality claim for the {50,20,10,5} denomination set was verified independently here via exhaustive dynamic-programming comparison over amounts 0–500 (zero greedy-suboptimal or greedy-fail cases); the {25,20,10}→40 counterexample is the canonical illustration that greedy is correct only for canonical denomination sets.

Interview drills & operability

Q1. How do you model the hardware?
Put each device behind an interface — CardReader, CashDispenser, ReceiptPrinter — so the session logic depends on the abstraction, not a driver. Tests inject fakes (a dispenser whose inventory you control); production injects the real drivers. This is the same "program to an interface" that lets you unit-test the change-making and state transitions with no physical machine.

Q2. What is the partial-dispense policy?
Cash is all-or-nothing: canDispense(amount) must confirm a full, valid bill combination before the account is debited, and only then does the dispenser release exactly those bills. Never debit-then-discover-you-can't-pay, and never hand out a partial amount without an explicit accounting-and-receipt policy — a partially-completed withdrawal that debited the account is the worst failure this design exists to prevent.

Q3. What breaks in production, and how do you fingerprint it?
Two operability traps: (a) PIN retries must be capped — lock or capture the card after N failures, or the machine is a brute-force oracle; (b) cassette counts must never go negative — decrement inventory under a lock so two concurrent sessions cannot both "dispense" the same physical notes. Field fingerprints of a broken build: negative cassette counters, a session stuck after cancel, or a printed receipt with no matching dispense.