Low-level design · Problem P08 of 15 · Classic systems

ATM

An ATM combines three ideas: a small state machine (no card, card in, authenticated), a boundary to the bank it must not bypass, and a chain of responsibility to make up an amount from notes, which must be planned before any money moves.

1. The prompt

The prompt"Design an ATM: insert a card, enter a PIN, check the balance, withdraw cash. It holds a limited number of notes of each denomination."

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

Ask	Assume (unless told otherwise)
Which notes?	$100, $50, $20 and $10, with limited counts.
Wrong PIN?	Three tries, then the card is kept.
Who holds balances?	The bank; the ATM asks over an interface.

Must do

Card and PIN, with a limit of three wrong PINs
Withdraw: check balance, make up the amount from notes, debit, dispense
Eject the card

Must be

Never debit without paying out, or pay out without debiting
Every action rejected cleanly in the wrong state
Easy to add a denomination

Out of scope

Deposits
Transfers
Receipts and screens

3. The classes

The class diagram: arrows show who uses or holds whom.

Class	Its one job
ATM	The session: which step it's in, which card, how many PIN tries
Bank	Verify a PIN, read a balance, debit; the ATM's only view of accounts
NoteDispenser	One denomination in the chain: plan how many of its notes to use, pass the rest on, and later commit

4. How it works

5. Patterns and why

Pattern	Where	Why it's worth it here
Chain of responsibility	NoteDispenser handlers, largest first	Adding a $5 note is one more link, no if-chain
Plan, then commit	plan() changes nothing; commit() after the debit	The machine never gives out notes it can't account for, or debits for notes it couldn't give
State (as an enum)	IDLE → CARD_IN → AUTHENTICATED	Each action checks the step first; small enough not to need state classes

Memory hook: "Plan the notes, debit, then pay"Ask the chain whether the amount can be made, take the money from the account, and only then count out the notes.

6. The code

The bank is an interface with an in-memory implementation. The dispensers form a chain from $100 down to $10.

from __future__ import annotations
from abc import ABC, abstractmethod
from enum import Enum, auto
from typing import Optional


class Bank(ABC):
    """The ATM never holds balances: it asks the bank."""

    @abstractmethod
    def verify(self, card: str, pin: str) -> bool: ...

    @abstractmethod
    def balance(self, card: str) -> int: ...

    @abstractmethod
    def debit(self, card: str, amount: int) -> None: ...


class InMemoryBank(Bank):
    def __init__(self) -> None:
        self.accounts: dict[str, list] = {}   # card -> [pin, balance]

    def open(self, card: str, pin: str, balance: int) -> None:
        self.accounts[card] = [pin, balance]

    def verify(self, card: str, pin: str) -> bool:
        return card in self.accounts and self.accounts[card][0] == pin

    def balance(self, card: str) -> int:
        return self.accounts[card][1]

    def debit(self, card: str, amount: int) -> None:
        if self.accounts[card][1] < amount:
            raise ValueError("insufficient funds")
        self.accounts[card][1] -= amount


class NoteDispenser:
    """Chain of responsibility: each handler takes what it can in its note, then passes the rest on."""

    def __init__(self, note: int, count: int, nxt: Optional[NoteDispenser] = None) -> None:
        self.note, self.count, self.next = note, count, nxt

    def plan(self, amount: int, out: dict[int, int]) -> int:
        """Fill `out` with notes to use; returns what's still left to pay. Changes nothing yet."""
        use = min(amount // self.note, self.count)
        if use:
            out[self.note] = use
        rest = amount - use * self.note
        return self.next.plan(rest, out) if self.next and rest else rest

    def commit(self, notes: dict[int, int]) -> None:
        self.count -= notes.get(self.note, 0)
        if self.next:
            self.next.commit(notes)


class Step(Enum):
    IDLE = auto()
    CARD_IN = auto()
    AUTHENTICATED = auto()


class ATM:
    MAX_PIN_TRIES = 3

    def __init__(self, bank: Bank, cash: NoteDispenser) -> None:
        self.bank, self.cash = bank, cash
        self.step, self.card, self.tries = Step.IDLE, None, 0

    def insert_card(self, card: str) -> str:
        if self.step is not Step.IDLE:
            return "a card is already inside"
        self.step, self.card, self.tries = Step.CARD_IN, card, 0
        return "enter PIN"

    def enter_pin(self, pin: str) -> str:
        if self.step is not Step.CARD_IN:
            return "insert a card first"
        if self.bank.verify(self.card, pin):
            self.step = Step.AUTHENTICATED
            return "PIN accepted"
        self.tries += 1
        if self.tries >= self.MAX_PIN_TRIES:
            self.step, self.card = Step.IDLE, None
            return "card retained: too many wrong PINs"
        return f"wrong PIN, {self.MAX_PIN_TRIES - self.tries} tries left"

    def withdraw(self, amount: int) -> str:
        if self.step is not Step.AUTHENTICATED:
            return "enter PIN first"
        if amount <= 0 or amount % 10:
            return "amount must be a positive multiple of 10"
        if self.bank.balance(self.card) < amount:
            return "insufficient funds"
        notes: dict[int, int] = {}
        if self.cash.plan(amount, notes):   # plan first: never debit what we can't pay out
            return "this machine can't make that amount"
        self.bank.debit(self.card, amount)
        self.cash.commit(notes)
        return "dispense " + " + ".join(f"{n}x${d}" for d, n in sorted(notes.items(), reverse=True))

    def eject(self) -> str:
        self.step, self.card = Step.IDLE, None
        return "card returned"


if __name__ == "__main__":
    bank = InMemoryBank()
    bank.open("4111", "2468", 1000)
    cash = NoteDispenser(100, 3, NoteDispenser(50, 2, NoteDispenser(20, 5, NoteDispenser(10, 5))))
    atm = ATM(bank, cash)
    print("withdraw 50:", atm.withdraw(50))
    print("insert card:", atm.insert_card("4111"))
    print("PIN 1111:", atm.enter_pin("1111"))
    print("PIN 2468:", atm.enter_pin("2468"))
    for amt in (370, 2000, 55, 160):
        print(f"withdraw {amt}:", atm.withdraw(amt))
    print("balance:", bank.balance("4111"))
    print("eject:", atm.eject())

/** The ATM never holds balances: it asks the bank. */
interface Bank {
  verify(card: string, pin: string): boolean;
  balance(card: string): number;
  debit(card: string, amount: number): void;
}

class InMemoryBank implements Bank {
  private accounts = new Map<string, { pin: string; balance: number }>();
  open(card: string, pin: string, balance: number): void { this.accounts.set(card, { pin, balance }); }
  verify(card: string, pin: string): boolean { return this.accounts.get(card)?.pin === pin; }
  balance(card: string): number { return this.accounts.get(card)!.balance; }
  debit(card: string, amount: number): void {
    const a = this.accounts.get(card)!;
    if (a.balance < amount) throw new Error("insufficient funds");
    a.balance -= amount;
  }
}

/** Chain of responsibility: each handler takes what it can in its note, then passes the rest on. */
class NoteDispenser {
  constructor(readonly note: number, private count: number, private next: NoteDispenser | null = null) {}

  /** Fill `out` with notes to use; returns what's still left to pay. Changes nothing yet. */
  plan(amount: number, out: Map<number, number>): number {
    const use = Math.min(Math.floor(amount / this.note), this.count);
    if (use) out.set(this.note, use);
    const rest = amount - use * this.note;
    return this.next && rest ? this.next.plan(rest, out) : rest;
  }

  commit(notes: Map<number, number>): void {
    this.count -= notes.get(this.note) ?? 0;
    this.next?.commit(notes);
  }
}

enum Step { IDLE, CARD_IN, AUTHENTICATED }

class ATM {
  static readonly MAX_PIN_TRIES = 3;
  private step = Step.IDLE;
  private card: string | null = null;
  private tries = 0;

  constructor(private bank: Bank, private cash: NoteDispenser) {}

  insertCard(card: string): string {
    if (this.step !== Step.IDLE) return "a card is already inside";
    [this.step, this.card, this.tries] = [Step.CARD_IN, card, 0];
    return "enter PIN";
  }

  enterPin(pin: string): string {
    if (this.step !== Step.CARD_IN) return "insert a card first";
    if (this.bank.verify(this.card!, pin)) {
      this.step = Step.AUTHENTICATED;
      return "PIN accepted";
    }
    if (++this.tries >= ATM.MAX_PIN_TRIES) {
      [this.step, this.card] = [Step.IDLE, null];
      return "card retained: too many wrong PINs";
    }
    return `wrong PIN, ${ATM.MAX_PIN_TRIES - this.tries} tries left`;
  }

  withdraw(amount: number): string {
    if (this.step !== Step.AUTHENTICATED) return "enter PIN first";
    if (amount <= 0 || amount % 10) return "amount must be a positive multiple of 10";
    if (this.bank.balance(this.card!) < amount) return "insufficient funds";
    const notes = new Map<number, number>();
    if (this.cash.plan(amount, notes)) return "this machine can't make that amount"; // plan first: never debit what we can't pay out
    this.bank.debit(this.card!, amount);
    this.cash.commit(notes);
    return "dispense " + [...notes.entries()].sort((a, b) => b[0] - a[0]).map(([d, n]) => `${n}x$${d}`).join(" + ");
  }

  eject(): string {
    [this.step, this.card] = [Step.IDLE, null];
    return "card returned";
  }
}

const bank = new InMemoryBank();
bank.open("4111", "2468", 1000);
const atm = new ATM(bank, new NoteDispenser(100, 3, new NoteDispenser(50, 2, new NoteDispenser(20, 5, new NoteDispenser(10, 5)))));
console.log("withdraw 50:", atm.withdraw(50));
console.log("insert card:", atm.insertCard("4111"));
console.log("PIN 1111:", atm.enterPin("1111"));
console.log("PIN 2468:", atm.enterPin("2468"));
for (const amt of [370, 2000, 55, 160]) console.log(`withdraw ${amt}:`, atm.withdraw(amt));
console.log("balance:", bank.balance("4111"));
console.log("eject:", atm.eject());

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

/** The ATM never holds balances: it asks the bank. */
interface Bank {
    boolean verify(String card, String pin);
    int balance(String card);
    void debit(String card, int amount);
}

class InMemoryBank implements Bank {
    private record Account(String pin, int[] balance) {}

    private final Map<String, Account> accounts = new HashMap<>();

    void open(String card, String pin, int balance) {
        accounts.put(card, new Account(pin, new int[] {balance}));
    }

    public boolean verify(String card, String pin) {
        Account a = accounts.get(card);
        return a != null && a.pin().equals(pin);
    }

    public int balance(String card) {
        return accounts.get(card).balance()[0];
    }

    public synchronized void debit(String card, int amount) {
        int[] b = accounts.get(card).balance();
        if (b[0] < amount) throw new IllegalStateException("insufficient funds");
        b[0] -= amount;
    }
}

/** Chain of responsibility: each handler takes what it can in its note, then passes the rest on. */
class NoteDispenser {
    private final int note;
    private int count;
    private final NoteDispenser next;

    NoteDispenser(int note, int count, NoteDispenser next) {
        this.note = note;
        this.count = count;
        this.next = next;
    }

    /** Fill out with notes to use; returns what's still left to pay. Changes nothing yet. */
    int plan(int amount, Map<Integer, Integer> out) {
        int use = Math.min(amount / note, count);
        if (use > 0) out.put(note, use);
        int rest = amount - use * note;
        return next != null && rest > 0 ? next.plan(rest, out) : rest;
    }

    void commit(Map<Integer, Integer> notes) {
        count -= notes.getOrDefault(note, 0);
        if (next != null) next.commit(notes);
    }
}

enum Step { IDLE, CARD_IN, AUTHENTICATED }

class ATM {
    static final int MAX_PIN_TRIES = 3;
    private final Bank bank;
    private final NoteDispenser cash;
    private Step step = Step.IDLE;
    private String card;
    private int tries;

    ATM(Bank bank, NoteDispenser cash) {
        this.bank = bank;
        this.cash = cash;
    }

    String insertCard(String c) {
        if (step != Step.IDLE) return "a card is already inside";
        step = Step.CARD_IN;
        card = c;
        tries = 0;
        return "enter PIN";
    }

    String enterPin(String pin) {
        if (step != Step.CARD_IN) return "insert a card first";
        if (bank.verify(card, pin)) {
            step = Step.AUTHENTICATED;
            return "PIN accepted";
        }
        if (++tries >= MAX_PIN_TRIES) {
            step = Step.IDLE;
            card = null;
            return "card retained: too many wrong PINs";
        }
        return "wrong PIN, " + (MAX_PIN_TRIES - tries) + " tries left";
    }

    String withdraw(int amount) {
        if (step != Step.AUTHENTICATED) return "enter PIN first";
        if (amount <= 0 || amount % 10 != 0) return "amount must be a positive multiple of 10";
        if (bank.balance(card) < amount) return "insufficient funds";
        Map<Integer, Integer> notes = new TreeMap<>(java.util.Comparator.reverseOrder());
        if (cash.plan(amount, notes) != 0) return "this machine can't make that amount"; // plan first: never debit what we can't pay out
        bank.debit(card, amount);
        cash.commit(notes);
        return "dispense " + notes.entrySet().stream().map(e -> e.getValue() + "x$" + e.getKey()).collect(Collectors.joining(" + "));
    }

    String eject() {
        step = Step.IDLE;
        card = null;
        return "card returned";
    }
}

public class Main {
    public static void main(String[] args) {
        InMemoryBank bank = new InMemoryBank();
        bank.open("4111", "2468", 1000);
        NoteDispenser cash = new NoteDispenser(100, 3, new NoteDispenser(50, 2, new NoteDispenser(20, 5, new NoteDispenser(10, 5, null))));
        ATM atm = new ATM(bank, cash);
        System.out.println("withdraw 50: " + atm.withdraw(50));
        System.out.println("insert card: " + atm.insertCard("4111"));
        System.out.println("PIN 1111: " + atm.enterPin("1111"));
        System.out.println("PIN 2468: " + atm.enterPin("2468"));
        for (int amt : new int[] {370, 2000, 55, 160}) System.out.println("withdraw " + amt + ": " + atm.withdraw(amt));
        System.out.println("balance: " + bank.balance("4111"));
        System.out.println("eject: " + atm.eject());
    }
}

Output (the same in all three languages)

withdraw 50: enter PIN first
insert card: enter PIN
PIN 1111: wrong PIN, 2 tries left
PIN 2468: PIN accepted
withdraw 370: dispense 3x$100 + 1x$50 + 1x$20
withdraw 2000: insufficient funds
withdraw 55: amount must be a positive multiple of 10
withdraw 160: dispense 1x$50 + 4x$20 + 3x$10
balance: 470
eject: card returned

7. Concurrency and edge cases

Debit and dispense must succeed or fail together. If the shutter jams after the debit, reverse the debit (a compensating credit) and log it for reconciliation.
The bank is remote: time out, retry with an idempotency key so a retried debit isn't applied twice.
Greedy can fail with limited notes: with only $50 and $20 notes, $60 needs three $20s but greedy takes a $50 first. If that matters, plan with a small search (dynamic programming over counts) instead of greedy.
One session at a time per machine; the bank's debit must be atomic across machines.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

How would you support deposits?: A deposit flow that counts notes in, credits the account as pending until verified, and adds the notes to the dispensers.
Daily withdrawal limits?: The bank enforces them (the ATM can be bypassed); the ATM shows the error.
Why not let the ATM keep balances?: Many ATMs and branches change the same account; one system of record (the bank) avoids conflicting copies.

9. Common mistakes

Dispensing before debitingIf the debit then fails, the money's gone.

Changing note counts during planningA failed plan must leave the machine exactly as it was.

No state checkswithdraw() before a PIN should be refused.

10. Check yourself

Why does the chain have a separate plan() and commit()?

All-or-nothing: plan first, then debit, then commit.

What pattern is the note chain?

Each handler does its part and passes the rest on.

Where should daily limits be enforced?

The system of record must enforce rules that matter across machines.

Your turn

Add a $5 note (5 min). One more link in the chain.
Make planning exact (20 min). Replace greedy with a search that finds any valid combination.