Design an ATM¶
TL;DR¶
- You build a state machine with a bank behind it: six
ATMStateclasses decide what is even offered,AtmTransactioncommands do the work, and aCashDispenserpicks the notes. - Three decisions carry the interview: reserve, dispense, commit (a jam rolls the reservation back, so nothing is debited), the account lock lives in the bank, not the machine (two ATMs, one account), and the denomination chain backtracks instead of being greedy.
- Patterns that earn their place: State, Chain of Responsibility, Command with Template Method, Facade, Factory. A
Keypadclass is deliberately absent.
Problem statement¶
"Design the software inside an ATM. A customer inserts a card, enters a PIN, and can check a balance, withdraw cash, deposit, transfer between their accounts and print a mini statement. Three wrong PINs block the card. Withdrawals respect a daily limit and can only pay amounts the machine's notes can make. Cash is finite and an engineer refills it. Tell me what happens when the machine debits the account and then fails to hand over the notes, and what happens when the same account is used at two machines at once."
Requirements¶
Functional
- Card in, PIN entry, three attempts, then the card is blocked and retained.
- Account selection when a card reaches more than one account; balance inquiry.
- Withdrawal with a per-account daily limit and physical note dispensing.
- Deposit, transfer between accounts, and a mini statement of the last transactions.
- Cancel and eject at any point where cancelling is safe; a printed receipt per transaction.
- Out-of-cash and out-of-service handling; an admin replenishes the cassettes.
Non-functional and constraints
- The account is never debited for money the customer did not receive, and never pays out money it did not debit.
- The same account used at two machines at once must not go below zero or past its daily limit.
- An abandoned session ends by itself and returns the card.
- In-memory, single process. The core banking system sits behind a
Protocol; the note feeder is an object you can replace with one that jams.
Out of scope: the physical hardware bus, card networks and EMV cryptography, cheque deposits, fraud scoring, multi-currency.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
| Is the machine online with the bank for every transaction? | Yes. Offline stand-in mode is a follow-up and changes the risk model completely. |
| What are the notes? | 100, 50, 20 and 10. The set is injected, so a machine with 2000s and 500s is a constructor argument. |
| Whose money is at risk if the dispenser jams? | The bank's, and that is the point. The design chooses "customer keeps the money in the account" over "machine keeps the notes". |
| Does the PIN attempt counter live in the machine or the bank? | The bank. A counter in the machine would reset by walking to the next ATM. |
| Is the daily limit per card or per account? | Per account, so two cards on a joint account share it. |
| What happens when the customer walks away? | A 90-second inactivity timeout ejects the card and drops the session. |
| Can one machine serve two customers at once? | No, and the lock enforces it - but the maintenance panel and the timeout watchdog are separate callers, so the lock is not ceremony. |
Core entities and relationships¶
- ATM — the State context. It owns the peripherals, the current state object, the selected account and the
RLockthat serialises everything. - ATMState (abstract) with
IdleState,CardInsertedState,AuthenticatedState,TransactingState,DispensingState,OutOfServiceState. The base refuses every operation; each subclass overrides only what it allows. - AtmTransaction (abstract) with
WithdrawalTransaction,DepositTransaction,TransferTransaction,BalanceInquiry, built byTransactionFactory.executeis a Template Method: validate, perform, print. - BankService (
Protocol) withInMemoryBank— the Facade over the core banking system. It ownsAccounts, one lock per account, the PIN attempt counters and the ledger. - Reservation — money held for a withdrawal that has not been dispensed yet. It is the object that makes the whole design atomic.
- CashDispenser — the cassettes, their lock, and the
NoteFeederthat stands in for the hardware. - DenominationHandler — one link per note value; the chain plans which notes to hand out.
- Screen, Printer, CardReader — the peripherals, so no flow ever calls
print.
Multiplicities: ATM 1 -> 1 state (shared instances), ATM 1 -> 1 dispenser, dispenser 1 -> * handlers in a chain, bank 1 -> * accounts, card 1 -> * accounts, account 1 -> * transaction records.
Class diagram¶
The machine: one context, six states, three peripherals.
classDiagram
class ATM {
+id: str
+state: AtmStateName
-lock: RLock
+insert_card(card) None
+enter_pin(pin) None
+withdraw(amount) Receipt
+deposit(amount) Receipt
+transfer(target_id, amount) Receipt
+cancel() None
+enter(name) None
+replenish(notes) Money
}
class ATMState {
<<abstract>>
+name: AtmStateName
+insert_card(atm, card) None
+enter_pin(atm, pin) None
+withdraw(atm, amount) Receipt
+cancel(atm) None
}
class IdleState
class CardInsertedState
class AuthenticatedState
class TransactingState
class DispensingState
class OutOfServiceState
class Screen
class Printer
class CardReader {
+accept(card) None
+eject() Card
+retain(card) None
}
class Card {
+number: str
+holder: str
+status: CardStatus
}
ATMState <|-- IdleState
ATMState <|-- CardInsertedState
ATMState <|-- AuthenticatedState
ATMState <|-- TransactingState
ATMState <|-- DispensingState
ATMState <|-- OutOfServiceState
ATM --> ATMState : current
ATM *-- Screen
ATM *-- Printer
ATM *-- CardReader
CardReader --> "0..1" CardThe work: transactions, the bank facade, and the note chain.
classDiagram
class AtmTransaction {
<<abstract>>
+transaction_type: TransactionType
+execute() Receipt
+validate() None
+perform() tuple
}
class WithdrawalTransaction
class DepositTransaction
class TransferTransaction
class BalanceInquiry
class TransactionFactory {
+create(transaction_type, atm, account_id, amount) AtmTransaction
}
class BankService {
<<interface>>
+authenticate(card_number, pin) tuple
+reserve(account_id, amount) Reservation
+commit(reservation) TransactionRecord
+release(reservation) None
+transfer(source_id, target_id, amount) TransactionRecord
}
class InMemoryBank {
-account_locks: Dict~str,Lock~
+open_account(account_id, holder, balance) Account
+reserved(account_id) Money
}
class Account {
+id: str
+balance: Money
+reserved: Money
+daily_withdrawn: Money
+available() Money
}
class Reservation {
+id: str
+amount: Money
}
class CashDispenser {
-inventory: Dict~Money,int~
-lock: Lock
+plan(amount) Dict~Money,int~
+dispense(amount) Dict~Money,int~
+replenish(notes) Money
}
class DenominationHandler {
+note: Money
+successor: DenominationHandler
+plan(amount, available) Dict~Money,int~
}
class NoteFeeder {
<<interface>>
+push(plan) None
}
AtmTransaction <|-- WithdrawalTransaction
AtmTransaction <|-- DepositTransaction
AtmTransaction <|-- TransferTransaction
AtmTransaction <|-- BalanceInquiry
TransactionFactory ..> AtmTransaction : creates
BankService <|.. InMemoryBank
InMemoryBank "1" *-- "many" Account
InMemoryBank ..> Reservation : issues
WithdrawalTransaction ..> CashDispenser
WithdrawalTransaction ..> BankService
CashDispenser --> DenominationHandler : head of chain
DenominationHandler --> "0..1" DenominationHandler : successor
CashDispenser --> NoteFeederDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| State | ATMState and its six subclasses |
The base class is a wall of refusals and each state overrides three or four methods, so "what can I do here" is answered by reading one short class. An enum plus if guards in every method would scatter the same table across a dozen places. |
| Chain of Responsibility | DenominationHandler per note, largest first |
Each link takes what it can and passes the remainder on. Adding a 5 note is one more link; the dispenser code does not change. |
| Command | AtmTransaction subclasses |
A transaction is an object, so it can be validated before it starts, logged, retried, or queued for an offline mode. |
| Template Method | AtmTransaction.execute = validate, perform, print |
The order is fixed for every transaction type and written once. Only the withdrawal overrides validate, because only it touches hardware. |
| Facade | BankService |
The real core banking system is many hosts; the machine sees eight methods. That is also what makes the whole package testable without a bank. |
| Factory Method | TransactionFactory, build_chain |
Adding "pay a bill" is one class and one registry line. |
| Flyweight | state_for interning one instance per state |
States hold no data, so every machine in the estate can share six objects. |
What was deliberately not used: a Keypad class. Interviewers expect the noun list from the problem statement to become classes; a keypad has no behaviour beyond "the PIN arrives as an argument", so modelling it adds a file and buys nothing. Say that out loud — knowing which nouns are not entities is the same skill as knowing which are. Also no Singleton for the dispenser: it is constructor-injected, so tests can hand the machine a feeder that jams.
Key flows¶
Withdrawal: plan, reserve, dispense, commit — and what happens when the notes stick.
sequenceDiagram
autonumber
actor C as Customer
participant A as ATM
participant S as AuthenticatedState
participant T as WithdrawalTransaction
participant B as BankService
participant D as CashDispenser
C->>A: withdraw(180)
A->>S: withdraw(atm, 180)
S->>T: execute()
T->>D: plan(180)
D-->>T: 1x100, 1x50, 1x20, 1x10
T->>B: reserve(ACC-1, 180)
B-->>T: Reservation
T->>A: enter(DISPENSING)
T->>D: dispense(180)
alt notes handed over
D-->>T: notes
T->>B: commit(reservation)
B-->>T: TransactionRecord
T-->>C: Receipt
else feeder jams
D-->>T: DispenserJamError
T->>B: release(reservation)
S->>A: go_out_of_service(fault)
T-->>C: DispenserJamError
endThe state machine. Note the two arrows that matter: TRANSACTING -> DISPENSING happens only after the money is reserved, and DISPENSING -> OUT_OF_SERVICE is the only place a fault takes the machine down.
stateDiagram-v2
[*] --> IDLE
IDLE --> CARD_INSERTED : card accepted
CARD_INSERTED --> IDLE : cancel or third wrong PIN
CARD_INSERTED --> AUTHENTICATED : PIN accepted
AUTHENTICATED --> TRANSACTING : transaction starts
TRANSACTING --> AUTHENTICATED : deposit, transfer or refusal
TRANSACTING --> DISPENSING : cash reserved
DISPENSING --> AUTHENTICATED : notes taken and committed
DISPENSING --> OUT_OF_SERVICE : note feeder jam
AUTHENTICATED --> IDLE : cancel, timeout or eject
OUT_OF_SERVICE --> IDLE : admin replenishImplementation¶
Build it in the order the money moves: the vocabulary, the cash, the transactions, the states, then the machine that hosts them.
The enums are the state names and the transaction taxonomy; the errors are what the screen turns into a message. Account is the first place the design shows: balance and reserved are separate fields, and available() is what everybody checks.
code/lld/atm/models.py — enums
class AtmStateName(StrEnum):
"""The six states a machine can be in. The classes live in ``states.py``."""
IDLE = "idle" # waiting for a card
CARD_INSERTED = "card_inserted" # card held, PIN not yet accepted
AUTHENTICATED = "authenticated" # a session is open on one account
TRANSACTING = "transacting" # a command is running against the bank
DISPENSING = "dispensing" # notes are moving; cancel is refused here
OUT_OF_SERVICE = "out_of_service" # jam or empty cassettes; only an admin gets out
class CardStatus(StrEnum):
ACTIVE = "active"
BLOCKED = "blocked" # three wrong PINs
RETAINED = "retained" # swallowed by the machine
class TransactionType(StrEnum):
WITHDRAWAL = "withdrawal"
DEPOSIT = "deposit"
TRANSFER = "transfer"
BALANCE_INQUIRY = "balance_inquiry"
class TransactionStatus(StrEnum):
COMMITTED = "committed"
ROLLED_BACK = "rolled_back"
code/lld/atm/models.py — errors
class AtmStateError(InvalidStateError):
"""The operation is not offered in the machine's current state."""
class SessionTimeoutError(InvalidStateError):
"""The customer walked away; the card was ejected and the session dropped."""
class InvalidPinError(ValidationError):
"""Wrong PIN; the message says how many attempts are left."""
class CardBlockedError(ConflictError):
"""Three wrong PINs, or a card the bank has already blocked."""
class InsufficientFundsError(ConflictError):
"""The available balance (balance minus reservations) is too small."""
class DailyLimitExceededError(ConflictError):
"""This withdrawal would push the account past its 24-hour cash limit."""
class DenominationError(ConflictError):
"""The amount cannot be built from the notes this machine holds."""
class OutOfCashError(ConflictError):
"""The cassettes hold less than the requested amount."""
class DispenserJamError(HandbookError):
"""The hardware failed while picking notes; nothing left the machine."""
class UnknownAccountError(NotFoundError):
"""No such account or card."""
code/lld/atm/models.py — entities
@dataclass(slots=True)
class Card:
number: str
holder: str
account_ids: tuple[str, ...]
status: CardStatus = CardStatus.ACTIVE
def is_usable(self) -> bool:
return self.status is CardStatus.ACTIVE
@dataclass(slots=True)
class Account:
"""Balance and reservations are separate on purpose.
``reserved`` is money promised to a withdrawal that has not been dispensed yet.
A second machine sees it immediately through ``available()``, which is how the
same account cannot be emptied twice at the same moment.
"""
id: str
holder: str
balance: Money
reserved: Money = Money(0)
daily_withdrawn: Money = Money(0)
daily_limit: Money = Money.of("500.00")
day_stamp: int = 0
def available(self) -> Money:
return self.balance - self.reserved
def remaining_daily(self) -> Money:
"""Reservations count against the limit exactly as they count against the balance.
Subtracting only ``daily_withdrawn`` would let two machines each reserve an
amount under the limit and then both commit, taking the account over it.
"""
return self.daily_limit - self.daily_withdrawn - self.reserved
@dataclass(frozen=True, slots=True)
class Reservation:
"""The receipt for step 1 of reserve-dispense-commit."""
id: str
account_id: str
amount: Money
created_at: float
@dataclass(frozen=True, slots=True)
class TransactionRecord:
id: str
type: TransactionType
account_id: str
amount: Money
balance_after: Money
at: float
status: TransactionStatus = TransactionStatus.COMMITTED
counterparty: str | None = None
def __str__(self) -> str:
target = f" -> {self.counterparty}" if self.counterparty else ""
return f"{self.id} {self.type}{target} {self.amount} balance {self.balance_after}"
@dataclass(frozen=True, slots=True)
class Receipt:
atm_id: str
record: TransactionRecord
notes: dict[Money, int] = field(default_factory=dict)
def note_summary(self) -> str:
if not self.notes:
return "no cash"
return ", ".join(f"{count}x{note}" for note, count in sorted(self.notes.items(), reverse=True))
def render(self) -> str:
return f"[{self.atm_id}] {self.record} ({self.note_summary()})"
The note chain. The version everybody writes is greedy — take as many 100s as fit, then 50s — and it is wrong: paying 60 out of one 50 and three 20s takes the 50 first and then fails with 10 left over. Counting down and backtracking when the rest of the chain cannot finish costs four lines.
code/lld/atm/dispenser.py — the chain
class DenominationHandler:
"""One link per note value: take what you can, hand the remainder to the next link.
The textbook version is greedy and *wrong*: paying 60 from one 50 and three 20s
fails if the 50 is taken first. Trying counts downwards and backtracking when the
rest of the chain cannot finish costs four lines and makes the answer correct.
"""
def __init__(self, note: Money, successor: DenominationHandler | None = None) -> None:
if note.cents <= 0:
raise ValidationError("a note must be worth something")
self.note = note
self.successor = successor
def plan(self, amount: Money, available: Mapping[Money, int]) -> dict[Money, int]:
"""Notes to hand out, or ``DenominationError`` if this chain cannot make the amount."""
if amount.is_zero():
return {}
most = min(amount.cents // self.note.cents, available.get(self.note, 0))
for count in range(most, -1, -1):
remainder = amount - self.note * count
if remainder.is_zero():
return {self.note: count} if count else {}
if self.successor is None:
continue
try:
rest = self.successor.plan(remainder, available)
except DenominationError:
continue # back up and try one note fewer
return {self.note: count, **rest} if count else rest
raise DenominationError(f"cannot make {amount} from the notes in the machine")
def build_chain(notes: tuple[Money, ...] = DEFAULT_NOTES) -> DenominationHandler:
"""Factory: build from the smallest note up, so the head of the chain is the largest."""
ordered = sorted(notes)
if not ordered:
raise ValidationError("a dispenser needs at least one denomination")
chain = DenominationHandler(ordered[0])
for note in ordered[1:]:
chain = DenominationHandler(note, chain)
return chain
The dispenser owns the cassettes and their lock. plan is the dry run the withdrawal uses to fail before any money is promised; dispense pushes the notes and only then decrements the counts.
code/lld/atm/dispenser.py — cassettes and hardware
class NoteFeeder(Protocol):
"""The hardware. Tests substitute one that jams."""
def push(self, plan: Mapping[Money, int]) -> None: ...
class ReliableFeeder:
def push(self, plan: Mapping[Money, int]) -> None:
return None
class CashDispenser:
"""Owns the cassettes and the lock that protects them.
``_lock`` guards the note counts: two machines never share a dispenser, but the
replenishing admin and a customer do, and a half-counted cassette is real money.
"""
def __init__(
self,
inventory: Mapping[Money, int],
feeder: NoteFeeder | None = None,
chain: DenominationHandler | None = None,
) -> None:
self._inventory: dict[Money, int] = dict(inventory)
self._feeder = feeder or ReliableFeeder()
self._chain = chain or build_chain(tuple(inventory))
self._lock = threading.Lock()
def total(self) -> Money:
with self._lock:
return self._total_unlocked()
def smallest_note(self) -> Money:
with self._lock:
return min(self._inventory)
def counts(self) -> dict[Money, int]:
with self._lock:
return dict(self._inventory)
def plan(self, amount: Money) -> dict[Money, int]:
"""What would come out, without moving a note. Raises before anything is reserved."""
with self._lock:
if amount > self._total_unlocked():
raise OutOfCashError(f"{self.__class__.__name__} holds {self._total_unlocked()}, less than {amount}")
return self._chain.plan(amount, self._inventory)
def dispense(self, amount: Money) -> dict[Money, int]:
"""Plan, push the notes, then decrement. A jam leaves the cassettes untouched."""
with self._lock:
if amount > self._total_unlocked():
raise OutOfCashError(f"cassettes hold {self._total_unlocked()}, less than {amount}")
plan = self._chain.plan(amount, self._inventory)
self._feeder.push(plan) # may raise DispenserJamError
for note, count in plan.items():
self._inventory[note] -= count
return plan
def replenish(self, notes: Mapping[Money, int]) -> Money:
with self._lock:
for note, count in notes.items():
if count < 0:
raise ValidationError("cannot replenish a negative number of notes")
self._inventory[note] = self._inventory.get(note, 0) + count
return self._total_unlocked()
def _total_unlocked(self) -> Money:
total = Money(0)
for note, count in self._inventory.items():
total = total + note * count
return total
class JammingFeeder:
"""Test/demo double: the pick roller fails before any note leaves the machine."""
def push(self, plan: Mapping[Money, int]) -> None:
raise DispenserJamError(f"note feeder jammed while picking {len(plan)} denomination(s)")
Now the transactions. execute is the same three steps for all of them; WithdrawalTransaction.perform is the sequence the whole problem is about.
code/lld/atm/transactions.py — the template and the withdrawal
class AtmTransaction(ABC):
"""Command + Template Method.
``execute`` is fixed: validate, perform, print. Subclasses own ``perform``; only
the withdrawal needs to touch the hardware, and only it overrides ``validate``.
"""
transaction_type: ClassVar[TransactionType]
def __init__(self, atm: ATM, account_id: str, amount: Money | None = None) -> None:
self.atm = atm
self.account_id = account_id
self.amount = amount
def execute(self) -> Receipt:
self.validate()
record, notes = self.perform()
receipt = Receipt(atm_id=self.atm.id, record=record, notes=notes)
self.atm.printer.print_receipt(receipt)
return receipt
def validate(self) -> None:
if self.amount is not None and self.amount.cents <= 0:
raise ValidationError(f"{self.transaction_type} amount must be positive")
@abstractmethod
def perform(self) -> tuple[TransactionRecord, dict[Money, int]]:
"""Do the work and return the ledger record plus any notes handed over."""
class WithdrawalTransaction(AtmTransaction):
"""The atomicity crux: reserve, dispense, commit - and roll back if the notes jam."""
transaction_type = TransactionType.WITHDRAWAL
def validate(self) -> None:
super().validate()
if self.amount is None:
raise ValidationError("a withdrawal needs an amount")
smallest = self.atm.dispenser.smallest_note()
if self.amount.cents % smallest.cents:
raise DenominationError(f"{self.amount} is not a multiple of {smallest}")
self.atm.dispenser.plan(self.amount) # fails now, before any money is promised
def perform(self) -> tuple[TransactionRecord, dict[Money, int]]:
bank, dispenser = self.atm.bank, self.atm.dispenser
amount = self.amount if self.amount is not None else Money(0)
reservation = bank.reserve(self.account_id, amount) # 1. promise the money
self.atm.enter(AtmStateName.DISPENSING)
try:
notes = dispenser.dispense(amount) # 2. hand it over
except Exception:
bank.release(reservation) # nothing left the machine, so un-promise it
raise
return bank.commit(reservation), notes # 3. only now is the balance really down
code/lld/atm/transactions.py — the other commands
class DepositTransaction(AtmTransaction):
transaction_type = TransactionType.DEPOSIT
def perform(self) -> tuple[TransactionRecord, dict[Money, int]]:
amount = self.amount if self.amount is not None else Money(0)
return self.atm.bank.deposit(self.account_id, amount), {}
class TransferTransaction(AtmTransaction):
transaction_type = TransactionType.TRANSFER
def __init__(self, atm: ATM, account_id: str, amount: Money | None, target_id: str) -> None:
super().__init__(atm, account_id, amount)
self.target_id = target_id
def perform(self) -> tuple[TransactionRecord, dict[Money, int]]:
amount = self.amount if self.amount is not None else Money(0)
return self.atm.bank.transfer(self.account_id, self.target_id, amount), {}
class BalanceInquiry(AtmTransaction):
transaction_type = TransactionType.BALANCE_INQUIRY
def perform(self) -> tuple[TransactionRecord, dict[Money, int]]:
return self.atm.bank.record_inquiry(self.account_id), {}
_TRANSACTIONS: dict[TransactionType, type[AtmTransaction]] = {
TransactionType.WITHDRAWAL: WithdrawalTransaction,
TransactionType.DEPOSIT: DepositTransaction,
TransactionType.TRANSFER: TransferTransaction,
TransactionType.BALANCE_INQUIRY: BalanceInquiry,
}
class TransactionFactory:
"""Adding "pay a bill" means one class and one line here - nothing else changes."""
@staticmethod
def create(
transaction_type: TransactionType, atm: ATM, account_id: str, amount: Money | None = None, **extra: str
) -> AtmTransaction:
klass = _TRANSACTIONS[transaction_type]
return klass(atm, account_id, amount, **extra)
The states. Read the base class first: every operation refuses, so a state that forgets to implement something fails loudly instead of doing damage.
code/lld/atm/states.py — the base and the first two states
class ATMState(ABC):
"""Default behaviour: refuse. Subclasses override only what they permit."""
name: ClassVar[AtmStateName]
def insert_card(self, atm: ATM, card: Card) -> None:
self._refuse("insert a card")
def enter_pin(self, atm: ATM, pin: str) -> None:
self._refuse("enter a PIN")
def select_account(self, atm: ATM, account_id: str) -> None:
self._refuse("select an account")
def check_balance(self, atm: ATM) -> Money:
self._refuse("check a balance")
def withdraw(self, atm: ATM, amount: Money) -> Receipt:
self._refuse("withdraw cash")
def deposit(self, atm: ATM, amount: Money) -> Receipt:
self._refuse("deposit cash")
def transfer(self, atm: ATM, target_id: str, amount: Money) -> Receipt:
self._refuse("transfer money")
def mini_statement(self, atm: ATM) -> list[TransactionRecord]:
self._refuse("print a statement")
def cancel(self, atm: ATM) -> None:
self._refuse("cancel")
def _refuse(self, action: str) -> NoReturn:
raise AtmStateError(f"cannot {action} while the machine is {self.name}")
class IdleState(ATMState):
name = AtmStateName.IDLE
def insert_card(self, atm: ATM, card: Card) -> None:
if not card.is_usable():
atm.reader.retain(card)
raise CardBlockedError(f"card {card.number} is {card.status}; retained")
atm.reader.accept(card)
atm.screen.show(f"welcome {card.holder}, enter your PIN")
atm.enter(AtmStateName.CARD_INSERTED)
def cancel(self, atm: ATM) -> None:
atm.screen.show("nothing to cancel")
class CardInsertedState(ATMState):
name = AtmStateName.CARD_INSERTED
def enter_pin(self, atm: ATM, pin: str) -> None:
card = atm.require_card()
try:
accounts = atm.bank.authenticate(card.number, pin)
except CardBlockedError:
atm.reader.retain(card)
atm.end_session()
raise
atm.begin_session(accounts)
atm.screen.show(f"accounts: {', '.join(accounts)}")
atm.enter(AtmStateName.AUTHENTICATED)
def cancel(self, atm: ATM) -> None:
atm.end_session()
code/lld/atm/states.py — the authenticated state and the rest
class AuthenticatedState(ATMState):
"""The only state that starts transactions. It owns the TRANSACTING/DISPENSING dance."""
name = AtmStateName.AUTHENTICATED
def select_account(self, atm: ATM, account_id: str) -> None:
atm.set_account(account_id)
def check_balance(self, atm: ATM) -> Money:
return atm.bank.balance(atm.require_account())
def mini_statement(self, atm: ATM) -> list[TransactionRecord]:
return atm.bank.statement(atm.require_account(), limit=5)
def withdraw(self, atm: ATM, amount: Money) -> Receipt:
return self._run(atm, TransactionType.WITHDRAWAL, amount)
def deposit(self, atm: ATM, amount: Money) -> Receipt:
return self._run(atm, TransactionType.DEPOSIT, amount)
def transfer(self, atm: ATM, target_id: str, amount: Money) -> Receipt:
return self._run(atm, TransactionType.TRANSFER, amount, target_id=target_id)
def cancel(self, atm: ATM) -> None:
atm.end_session()
def _run(
self, atm: ATM, transaction_type: TransactionType, amount: Money, **extra: str
) -> Receipt:
transaction = TransactionFactory.create(
transaction_type, atm, atm.require_account(), amount, **extra
)
atm.enter(AtmStateName.TRANSACTING)
try:
receipt = transaction.execute()
except DispenserJamError as exc:
# The money is already un-reserved; the machine, however, is broken.
atm.go_out_of_service(str(exc))
raise
except Exception:
atm.enter(AtmStateName.AUTHENTICATED) # a refusal keeps the session open
raise
atm.enter(AtmStateName.AUTHENTICATED)
return receipt
class TransactingState(ATMState):
"""Transient. A second request arriving now is refused rather than queued."""
name = AtmStateName.TRANSACTING
class DispensingState(ATMState):
"""Transient, and deliberately without ``cancel``: notes are already moving."""
name = AtmStateName.DISPENSING
class OutOfServiceState(ATMState):
name = AtmStateName.OUT_OF_SERVICE
def insert_card(self, atm: ATM, card: Card) -> None:
raise AtmStateError(f"{atm.id} is out of service: {atm.fault or 'unknown fault'}")
_STATES: dict[AtmStateName, ATMState] = {
AtmStateName.IDLE: IdleState(),
AtmStateName.CARD_INSERTED: CardInsertedState(),
AtmStateName.AUTHENTICATED: AuthenticatedState(),
AtmStateName.TRANSACTING: TransactingState(),
AtmStateName.DISPENSING: DispensingState(),
AtmStateName.OUT_OF_SERVICE: OutOfServiceState(),
}
def state_for(name: AtmStateName) -> ATMState:
"""States hold no data, so one instance each is shared by every machine (Flyweight)."""
return _STATES[name]
The bank is a Facade with one lock per account. reserve, commit and release are the three methods worth reading twice.
code/lld/atm/bank.py
class BankService(Protocol):
"""What the machine needs from the core banking system - nothing more.
A Facade: the real thing is a dozen hosts and a message queue. The ATM sees
eight methods, which is also what makes it testable.
"""
def authenticate(self, card_number: str, pin: str) -> tuple[str, ...]: ...
def balance(self, account_id: str) -> Money: ...
def reserve(self, account_id: str, amount: Money) -> Reservation: ...
def commit(self, reservation: Reservation) -> TransactionRecord: ...
def release(self, reservation: Reservation) -> None: ...
def deposit(self, account_id: str, amount: Money) -> TransactionRecord: ...
def transfer(self, source_id: str, target_id: str, amount: Money) -> TransactionRecord: ...
def statement(self, account_id: str, limit: int) -> list[TransactionRecord]: ...
class InMemoryBank:
"""One lock per account, plus one registry lock for the shared dictionaries.
Transfers take two account locks, always in id order, so two opposite transfers
can never deadlock.
"""
MAX_PIN_ATTEMPTS = 3
def __init__(self, clock: Clock | None = None, ids: IdGenerator | None = None) -> None:
self._clock = clock or SystemClock()
self._ids = ids or SequentialIdGenerator("TXN")
self._accounts: dict[str, Account] = {}
self._account_locks: dict[str, threading.Lock] = {}
self._cards: dict[str, Card] = {}
self._pins: dict[str, str] = {}
self._attempts: dict[str, int] = {}
self._reservations: dict[str, Reservation] = {}
self._ledger: dict[str, list[TransactionRecord]] = {}
self._registry_lock = threading.Lock()
# -- setup -------------------------------------------------------------------------
def open_account(self, account_id: str, holder: str, balance: Money, **limits: Money) -> Account:
account = Account(id=account_id, holder=holder, balance=balance, **limits)
with self._registry_lock:
self._accounts[account_id] = account
self._account_locks[account_id] = threading.Lock()
self._ledger[account_id] = []
return account
def issue_card(self, number: str, holder: str, pin: str, account_ids: tuple[str, ...]) -> Card:
card = Card(number=number, holder=holder, account_ids=account_ids)
with self._registry_lock:
self._cards[number] = card
self._pins[number] = pin
return card
# -- authentication ----------------------------------------------------------------
def authenticate(self, card_number: str, pin: str) -> tuple[str, ...]:
with self._registry_lock:
card = self._cards.get(card_number)
if card is None:
raise UnknownAccountError(f"unknown card {card_number}")
if not card.is_usable():
raise CardBlockedError(f"card {card_number} is {card.status}")
if self._pins[card_number] != pin:
self._attempts[card_number] = self._attempts.get(card_number, 0) + 1
left = self.MAX_PIN_ATTEMPTS - self._attempts[card_number]
if left <= 0:
card.status = CardStatus.BLOCKED
raise CardBlockedError(f"card {card_number} blocked after {self.MAX_PIN_ATTEMPTS} attempts")
raise InvalidPinError(f"wrong PIN, {left} attempt(s) left")
self._attempts.pop(card_number, None)
return card.account_ids
# -- reserve, commit, release ------------------------------------------------------
def reserve(self, account_id: str, amount: Money) -> Reservation:
"""Hold the money before a single note moves. Visible to every other machine."""
account = self._account(account_id)
with self._lock_for(account_id):
self._roll_day(account)
if amount > account.available():
raise InsufficientFundsError(f"{account_id} has {account.available()} available, needs {amount}")
if amount > account.remaining_daily():
raise DailyLimitExceededError(
f"{account_id} may still take {account.remaining_daily()} today, not {amount}"
)
account.reserved = account.reserved + amount
reservation = Reservation(self._ids.next_id(), account_id, amount, self._clock.now())
with self._registry_lock:
self._reservations[reservation.id] = reservation
return reservation
def commit(self, reservation: Reservation) -> TransactionRecord:
self._take_reservation(reservation)
account = self._account(reservation.account_id)
with self._lock_for(account.id):
account.reserved = account.reserved - reservation.amount
account.balance = account.balance - reservation.amount
account.daily_withdrawn = account.daily_withdrawn + reservation.amount
return self._record(TransactionType.WITHDRAWAL, account, reservation.amount)
def release(self, reservation: Reservation) -> None:
"""Undo step 1. Idempotent: a retry after a jam must not credit twice."""
self._take_reservation(reservation)
account = self._account(reservation.account_id)
with self._lock_for(account.id):
account.reserved = account.reserved - reservation.amount
self._record(
TransactionType.WITHDRAWAL, account, reservation.amount, status=TransactionStatus.ROLLED_BACK
)
# -- other transactions ------------------------------------------------------------
def balance(self, account_id: str) -> Money:
with self._lock_for(account_id):
return self._account(account_id).balance
def reserved(self, account_id: str) -> Money:
"""Money promised to a withdrawal in flight. Should be zero between customers."""
with self._lock_for(account_id):
return self._account(account_id).reserved
def deposit(self, account_id: str, amount: Money) -> TransactionRecord:
account = self._account(account_id)
with self._lock_for(account_id):
account.balance = account.balance + amount
return self._record(TransactionType.DEPOSIT, account, amount)
def transfer(self, source_id: str, target_id: str, amount: Money) -> TransactionRecord:
if source_id == target_id:
raise ValidationError("cannot transfer to the same account")
source, target = self._account(source_id), self._account(target_id)
first, second = sorted((source_id, target_id)) # fixed lock order, no deadlock
with self._lock_for(first), self._lock_for(second):
if amount > source.available():
raise InsufficientFundsError(f"{source_id} has {source.available()}, needs {amount}")
source.balance = source.balance - amount
target.balance = target.balance + amount
self._record(TransactionType.TRANSFER, target, amount, counterparty=source_id)
return self._record(TransactionType.TRANSFER, source, amount, counterparty=target_id)
def record_inquiry(self, account_id: str) -> TransactionRecord:
account = self._account(account_id)
with self._lock_for(account_id):
return self._record(TransactionType.BALANCE_INQUIRY, account, Money(0))
def statement(self, account_id: str, limit: int = 5) -> list[TransactionRecord]:
with self._registry_lock:
return list(self._ledger.get(account_id, []))[-limit:]
# -- internals ---------------------------------------------------------------------
def _account(self, account_id: str) -> Account:
with self._registry_lock:
account = self._accounts.get(account_id)
if account is None:
raise UnknownAccountError(f"unknown account {account_id}")
return account
def _lock_for(self, account_id: str) -> threading.Lock:
with self._registry_lock:
lock = self._account_locks.get(account_id)
if lock is None:
raise UnknownAccountError(f"unknown account {account_id}")
return lock
def _take_reservation(self, reservation: Reservation) -> None:
with self._registry_lock:
if self._reservations.pop(reservation.id, None) is None:
raise ConflictError(f"reservation {reservation.id} was already settled")
def _roll_day(self, account: Account) -> None:
today = int(self._clock.now() // SECONDS_PER_DAY)
if account.day_stamp != today:
account.day_stamp = today
account.daily_withdrawn = Money(0)
def _record(
self,
transaction_type: TransactionType,
account: Account,
amount: Money,
status: TransactionStatus = TransactionStatus.COMMITTED,
counterparty: str | None = None,
) -> TransactionRecord:
record = TransactionRecord(
id=self._ids.next_id(),
type=transaction_type,
account_id=account.id,
amount=amount,
balance_after=account.balance,
at=self._clock.now(),
status=status,
counterparty=counterparty,
)
with self._registry_lock:
self._ledger.setdefault(account.id, []).append(record)
return record
Finally the machine itself. Every keypad entry point is two lines: take the lock, delegate to the current state. The _session context manager is where the inactivity timeout lives, so no operation can forget it.
code/lld/atm/services.py — the ATM
class ATM:
"""The State context. One RLock serialises the whole machine.
A physical ATM has one customer at a time, but the software has several callers:
the customer's keypad, the maintenance panel and a session-timeout watchdog. The
lock is what stops the watchdog from ejecting the card mid-dispense.
"""
SESSION_TIMEOUT_SECONDS = 90.0
def __init__(
self,
atm_id: str,
bank: BankService,
dispenser: CashDispenser,
screen: Screen | None = None,
printer: Printer | None = None,
reader: CardReader | None = None,
clock: Clock | None = None,
) -> None:
self.id = atm_id
self.bank = bank
self.dispenser = dispenser
self.screen = screen or Screen()
self.printer = printer or Printer()
self.reader = reader or CardReader()
self.fault: str | None = None
self._clock = clock or SystemClock()
self._state: ATMState = state_for(AtmStateName.IDLE)
self._accounts: tuple[str, ...] = ()
self._selected: str | None = None
self._last_activity = self._clock.now()
self._lock = threading.RLock()
# -- the public keypad API ---------------------------------------------------------
def insert_card(self, card: Card) -> None:
with self._session() as state:
state.insert_card(self, card)
def enter_pin(self, pin: str) -> None:
with self._session() as state:
state.enter_pin(self, pin)
def select_account(self, account_id: str) -> None:
with self._session() as state:
state.select_account(self, account_id)
def check_balance(self) -> Money:
with self._session() as state:
return state.check_balance(self)
def withdraw(self, amount: Money) -> Receipt:
with self._session() as state:
return state.withdraw(self, amount)
def deposit(self, amount: Money) -> Receipt:
with self._session() as state:
return state.deposit(self, amount)
def transfer(self, target_id: str, amount: Money) -> Receipt:
with self._session() as state:
return state.transfer(self, target_id, amount)
def mini_statement(self) -> list[TransactionRecord]:
with self._session() as state:
return state.mini_statement(self)
def cancel(self) -> None:
with self._session() as state:
state.cancel(self)
# -- state plumbing ----------------------------------------------------------------
@property
def state(self) -> AtmStateName:
with self._lock:
return self._state.name
def enter(self, name: AtmStateName) -> None:
with self._lock:
self._state = state_for(name)
def begin_session(self, account_ids: tuple[str, ...]) -> None:
self._accounts = account_ids
self._selected = account_ids[0] if account_ids else None
def set_account(self, account_id: str) -> None:
"""Called by ``AuthenticatedState``; the keypad entry point is ``select_account``."""
if account_id not in self._accounts:
raise UnknownAccountError(f"card does not reach account {account_id}")
self._selected = account_id
def end_session(self) -> Card | None:
card = self.reader.eject()
self._accounts, self._selected = (), None
self.screen.show("card returned")
self.enter(AtmStateName.IDLE)
return card
def go_out_of_service(self, fault: str) -> None:
self.fault = fault
self.reader.eject()
self._accounts, self._selected = (), None
self.screen.show(f"out of service: {fault}")
self.enter(AtmStateName.OUT_OF_SERVICE)
def replenish(self, notes: Mapping[Money, int]) -> Money:
"""Admin action: refill the cassettes and bring the machine back."""
with self._lock:
total = self.dispenser.replenish(notes)
self.fault = None
self.enter(AtmStateName.IDLE)
return total
def require_card(self) -> Card:
card = self.reader.card
if card is None:
raise AtmStateError("no card in the reader")
return card
def require_account(self) -> str:
if self._selected is None:
raise AtmStateError("no account selected")
return self._selected
@contextmanager
def _session(self) -> Iterator[ATMState]:
"""Lock, expire an abandoned session, run the operation, then stamp the activity."""
with self._lock:
self._expire_if_abandoned()
try:
yield self._state
finally:
self._last_activity = self._clock.now()
def _expire_if_abandoned(self) -> None:
idle_for = self._clock.now() - self._last_activity
if self._state.name in (AtmStateName.IDLE, AtmStateName.OUT_OF_SERVICE):
return
if idle_for > self.SESSION_TIMEOUT_SECONDS:
self.end_session()
raise SessionTimeoutError(f"session dropped after {idle_for:.0f}s; card returned")
python -m lld.atm.demo runs one customer across two machines:
atm-1 is idle with 2800.00 USD in the cassettes
atm-1: wrong PIN, 2 attempt(s) left
atm-1 is authenticated: accounts: ACC-1, ACC-2
balance of ACC-1: 1200.00 USD
withdrew 180 -> 1x100.00 USD, 1x50.00 USD, 1x20.00 USD, 1x10.00 USD, balance 1020.00 USD
25.00 refused: 25.00 USD is not a multiple of 10.00 USD
400.00 refused: ACC-1 may still take 320.00 USD today, not 400.00 USD
deposit 300 -> balance 1320.00 USD
transfer 200 -> ACC-1 1120.00 USD, ACC-2 700.00 USD
mini statement: 3 entries, last transfer
atm-1 is idle again: card returned
atm-2: note feeder jammed while picking 1 denomination(s)
atm-2 is out_of_service; ACC-1 still holds 1120.00 USD (was 1120.00 USD)
admin replenish -> atm-2 is idle with 3800.00 USD
Concurrency and edge cases¶
Which lock protects what. Three, and they are at three different levels:
ATM._lock(anRLock) serialises one machine. A physical ATM serves one customer, but the software has three callers: the keypad, the maintenance panel, and the inactivity watchdog. Without the lock the watchdog can eject the card betweenreserveanddispense. It is re-entrant because a state calls back intoatm.enter(...)while the outer call still holds it.InMemoryBank._account_locks[id]— one lock per account, held for the balance read and the write. This is the lock that makes the two-machine case correct, and it is deliberately not in the ATM: the account is shared, the machine is not.transfertakes two of them in sorted id order, so opposite transfers between the same pair cannot deadlock.CashDispenser._lock— the note counts. The customer and the replenishing engineer touch the same cassettes, and a half-counted cassette is real money.
There is also one ordering rule to state out loud: an account lock may be taken before the registry lock, never the other way round.
The race it prevents. Two machines, one account with 500, both asked for 100 at the same moment. reserve runs inside the account lock and checks available() = balance - reserved, so the second caller sees the first one's reservation immediately. The concurrency test fires 16 withdrawals of 100 through two machines and asserts exactly five succeed and the balance lands on zero — never below.
Debit versus dispense. The failure everyone has met in real life is "the account was debited and no cash came out". This design cannot produce it, because the balance only moves in commit, which runs after the notes are out. The mirror failure ("cash out, no debit") is prevented by reserving first: the money is already unavailable to any other machine before a note moves. The residual risk is a partial dispense — the feeder hands over two notes of four and dies. Real machines solve this with a note counter and a reconciliation record; here NoteFeeder.push either succeeds or raises before anything leaves, and the honest answer in the room is "I would model a partial dispense as a DiscrepancyRecord the machine writes before going out of service, and reconcile against the physical count at replenishment".
Cost check. A withdrawal makes two calls to the bank (reserve and commit) instead of one. At the estimation cheatsheet's 500 µs same-datacenter round trip that is 1 ms instead of 0.5 ms, against a dispenser that takes seconds to count notes — a rounding error for a guarantee you cannot get any other way. The locks are cheaper still: an uncontended mutex is 17 ns.
Other edge cases handled: three wrong PINs block the card in the bank (a counter in the machine resets by walking to the next ATM) and the reader retains it; the daily limit resets on a day boundary computed from the injected clock as now // 86400, so tests advance one day instead of sleeping; an amount that is not a multiple of the smallest note is refused with a message that says which note; out-of-cash is checked against the cassette total before the chain runs; money that is only reserved still counts against the daily limit, so two machines cannot each stay under it and jointly go over; cancelling is offered while the machine is IDLE, CARD_INSERTED or AUTHENTICATED and falls through to the base class's refusal in TRANSACTING, DISPENSING and OUT_OF_SERVICE — once a command is running, notes may already be moving; a refusal keeps the session open, a jam does not.
Common mistake
Debiting the account first and dispensing afterwards, "because the bank call can fail". It can, but so can the hardware, and the hardware fails after you have already taken the money. The order that survives review is: plan the notes (fail cheap), reserve (fail cheap), dispense (fail expensive), commit (cannot fail). The second common mistake is putting the account lock in the ATM — it looks like it works until the interviewer says "now there are two machines", and then nothing protects the balance.
Extensibility and follow-ups¶
- Cardless withdrawal: the bank issues a one-time code bound to an account and amount.
IdleStategrows anenter_codepath that produces the same authenticated session; every state and transaction below it is unchanged. - Fraud checks: a second chain, this time of rules (velocity, geography, amount), consulted inside
WithdrawalTransaction.validate. Chain of Responsibility again, which is a nice thing to point out — the pattern is already in the codebase. - Offline / stand-in mode: the transactions are already Command objects, so queue them with a conservative local limit and replay on reconnection. Say the risk out loud: stand-in mode trades correctness for availability, and the bank absorbs the difference.
- Audit log: every
TransactionRecordalready carries an injected timestamp and a status includingROLLED_BACK; append them to a write-ahead log beforecommitand the machine can be reconciled after a power cut. - A new note denomination: one more
DenominationHandlerinbuild_chain. - Estate-wide monitoring (cash forecasting, remote diagnostics) is the point where this becomes an HLD conversation about telemetry ingestion.
Interview tip
When the interviewer asks "what if the dispenser jams", do not answer with a try/except. Answer with the sequence: "plan, reserve, dispense, commit — the balance moves last, so a jam releases the reservation and the customer keeps their money." Then say what you would do about a partial dispense. Naming the failure you cannot fully solve is worth more than pretending the happy path covers it.
Tests¶
tests/test_atm.py has 11 cases (17 with parametrisation), one per risk: a withdrawal dispenses the right notes and debits exactly once; three wrong PINs block and retain the card; every operation is refused in the states that do not offer it; the note chain is checked against five amounts including the one greedy gets wrong; the daily limit is shared across machines, counts money that is only reserved, and resets on a new day; out-of-cash is detected before anything is reserved; an idle session times out and returns the card; a transfer records both sides.
The jam test is the one to walk through — it asserts all four invariants at once:
code/lld/atm/tests/test_atm.py — a jam changes nothing
def test_a_jam_rolls_the_reservation_back_and_takes_the_machine_out_of_service(
clock: FakeClock,
) -> None:
bank, card = build(clock, balance="500.00")
atm = signed_in(bank, card, clock, feeder=JammingFeeder())
with pytest.raises(DispenserJamError):
atm.withdraw(Money.of("100.00"))
assert bank.balance("ACC-1") == Money.of("500.00") # money promised, never debited
assert bank.reserved("ACC-1") == Money(0) # and the promise was released
assert atm.dispenser.total() == Money.of("1800.00") # no note left the cassettes
assert atm.state is AtmStateName.OUT_OF_SERVICE
ledger = bank.statement("ACC-1", limit=5)
assert ledger[-1].status is TransactionStatus.ROLLED_BACK
assert atm.replenish({HUNDRED: 5}) == Money.of("2300.00")
assert atm.state is AtmStateName.IDLE
And the concurrency test states the invariant as arithmetic: 500 in the account, 16 attempts of 100, exactly five winners.
code/lld/atm/tests/test_atm.py — two machines, one account
def test_two_machines_never_overdraw_the_same_account(clock: FakeClock) -> None:
# 500 in the account, a limit high enough not to interfere, 16 attempts of 100.
bank, card = build(clock, balance="500.00", daily_limit=Money.of("5000.00"))
second_card = bank.issue_card("CARD-2", "Ada", pin="4321", account_ids=("ACC-1",))
atms = [
signed_in(bank, card, clock, atm_id="atm-1"),
signed_in(bank, second_card, clock, atm_id="atm-2"),
]
def withdraw(i: int) -> Money | None:
try:
return atms[i % 2].withdraw(Money.of("100.00")).record.amount
except InsufficientFundsError:
return None
with ThreadPoolExecutor(max_workers=8) as pool:
results = list(pool.map(withdraw, range(16)))
assert sum(1 for r in results if r is not None) == 5 # 500 / 100, not one note more
assert bank.balance("ACC-1") == Money(0)
assert bank.reserved("ACC-1") == Money(0)
Run them with uv run pytest code/lld/atm -q. Everything is deterministic: FakeClock drives the timeout and the day boundary, and JammingFeeder is a four-line class that makes a hardware failure a first-class test case.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0-5 | Clarify | Online or offline? Which notes? Daily limit per card or account? Who owns the PIN counter? Out of scope: EMV, cheques, fraud. |
| 5-10 | Entities and states | List the six states first — they are the spine of this problem. Then ATM, Card, Account, BankService, CashDispenser, transactions. |
| 10-16 | Class diagram | Draw the State hierarchy and the transaction hierarchy side by side. Mark the three locks. |
| 16-24 | The withdrawal flow | Write WithdrawalTransaction.perform and say "reserve, dispense, commit" as you write each line. This is the part they are grading. |
| 24-32 | The dispenser | Write DenominationHandler.plan, then break it: 60 from one 50 and three 20s. Add the backtracking. |
| 32-40 | Concurrency | Two machines on one account: where is the lock, and why is it in the bank? Then the jam path and out-of-service. |
| 40-45 | Extensions | Cardless codes, fraud rules as a second chain, offline stand-in and its risk, audit log. |
Related¶
- State — the pattern behind the six machine states
- Chain of Responsibility — the note-planning chain
- Template Method — validate, perform, print
- Design a vending machine (and a coffee machine) — the same state machine with change-making instead of notes
- Design a payment gateway and digital wallet — reserve and capture at the other end of the same money movement
- Design a parking lot — the same reserve-charge-commit shape on a smaller problem