0

Design an ATM

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Design an ATM

Companies: Amazon

Difficulty: Medium

Problem statement

Model an ATM: card and PIN authentication, balance inquiry, withdrawal with a cash dispenser of fixed denominations, deposit, and failure handling.

Requirements

  • One ATM serves one customer session at a time. Amounts are integers (no floats).
  • Insert card, enter PIN. Three wrong PINs in a row retain the card and end the session.
  • Once authenticated: balance inquiry, withdrawal, deposit, eject card; several transactions per session, staying in AUTHENTICATED.
  • Withdrawal: amount must be positive, payable with the notes in the cassettes (fixed denominations, e.g. 50 and 20), and approved by the bank.
  • Deposit: the note acceptor counts the cash; the bank credits the account (pending until verified).
  • Failures: insufficient funds, an amount the cassettes cannot make, bank unreachable, dispenser jam. Invariant: no debit without cash out, no cash out without a debit.
  • Out of scope: card network protocol, PIN encryption hardware, receipts, transfers, multi-currency, admin UI. The bank sits behind an interface.

Core objects

  • ATM — session state machine and facade; orchestrates bank and dispenser; keeps a journal and a store-and-forward reversals queue.
  • AtmState (enum) — IDLE, CARD_INSERTED, AUTHENTICATED, OUT_OF_SERVICE.
  • Card — card number and linked account id.
  • BankService (interface) — PIN check, balance, two-phase debit (hold / commit / release), deposit. InMemoryBank is its test double.
  • CashDispenser — note inventory per denomination; finds a note mix, reserves it, ejects it.
  • AtmError — every refusal shown to the customer.

Class design

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"atm","x":0,"y":100,"width":280,"height":170,"label":{"text":"ATM\nstate, card, tries\njournal, reversals\ninsert_card(), enter_pin()\nbalance(), withdraw()\ndeposit(), eject_card()"}},
 {"type":"rectangle","id":"bank","x":560,"y":0,"width":260,"height":150,"label":{"text":"BankService\n(interface)\nverify_pin(), balance()\nhold(), commit()\nrelease(), deposit()"}},
 {"type":"rectangle","id":"inmem","x":1060,"y":40,"width":200,"height":70,"label":{"text":"InMemoryBank"}},
 {"type":"rectangle","id":"disp","x":560,"y":230,"width":260,"height":120,"label":{"text":"CashDispenser\ncassettes, jammed\nreserve(), restock()\neject()"}},
 {"type":"rectangle","id":"state","x":0,"y":400,"width":180,"height":70,"label":{"text":"AtmState"}},
 {"type":"rectangle","id":"card","x":260,"y":400,"width":180,"height":70,"label":{"text":"Card"}},
 {"type":"arrow","id":"atm-bank","x":280,"y":145,"width":280,"height":-70,"start":{"id":"atm"},"end":{"id":"bank"},"label":{"text":"uses"}},
 {"type":"arrow","id":"atm-disp","x":280,"y":225,"width":280,"height":65,"start":{"id":"atm"},"end":{"id":"disp"},"label":{"text":"owns"}},
 {"type":"arrow","id":"inmem-bank","x":1060,"y":75,"width":-240,"height":0,"start":{"id":"inmem"},"end":{"id":"bank"},"label":{"text":"implements"}},
 {"type":"arrow","id":"atm-state","x":90,"y":270,"width":1,"height":130,"start":{"id":"atm"},"end":{"id":"state"},"label":{"text":"uses"}},
 {"type":"arrow","id":"atm-card","x":220,"y":270,"width":130,"height":130,"start":{"id":"atm"},"end":{"id":"card"},"label":{"text":"uses"}}
]}

Key flows

Authenticate. insert_card (only in IDLE) stores the card and resets tries. enter_pin calls BankService.verify_pin; success moves to AUTHENTICATED. The third failure retains the card, journals it, and returns to IDLE.

Withdraw (two-phase).

  1. ATM checks the state and that amount > 0.
  2. CashDispenser.reserve finds a note mix (large notes first, with backtracking: greedy fails on 60 with 50s and 20s) and removes those notes from the count. No mix: refuse, nothing else changed.
  3. BankService.hold(account, amount, txn_id). Declined: restock, "insufficient funds". Timeout: restock, queue txn_id in reversals (the hold may have landed), "bank unavailable".
  4. CashDispenser.eject. Jam: queue the reversal, journal it, return the card, go OUT_OF_SERVICE. The reserved notes stay out of the count until a technician reconciles the cassette.
  5. BankService.commit(txn_id) turns the hold into a debit; journal it.

Deposit. Check state and amount, BankService.deposit with a fresh txn id, journal it. Eject / timeout: eject_card returns to IDLE from either card state; a session timer calls the same method.

{"type":"excalidraw","elements":[
 {"type":"ellipse","id":"init","x":0,"y":160,"width":100,"height":50,"label":{"text":"start"}},
 {"type":"rectangle","id":"idle","x":200,"y":150,"width":180,"height":70,"label":{"text":"IDLE"}},
 {"type":"rectangle","id":"ci","x":620,"y":150,"width":240,"height":70,"label":{"text":"CARD_INSERTED"}},
 {"type":"rectangle","id":"auth","x":1100,"y":150,"width":240,"height":70,"label":{"text":"AUTHENTICATED"}},
 {"type":"rectangle","id":"oos","x":1090,"y":400,"width":260,"height":70,"label":{"text":"OUT_OF_SERVICE"}},
 {"type":"arrow","id":"init-idle","x":100,"y":185,"width":100,"height":0,"start":{"id":"init"},"end":{"id":"idle"}},
 {"type":"arrow","id":"idle-ci","x":380,"y":185,"width":240,"height":0,"start":{"id":"idle"},"end":{"id":"ci"},"label":{"text":"insert_card"}},
 {"type":"arrow","id":"ci-auth","x":860,"y":185,"width":240,"height":0,"start":{"id":"ci"},"end":{"id":"auth"},"label":{"text":"correct PIN"}},
 {"type":"arrow","id":"ci-idle","x":740,"y":220,"width":-450,"height":0,"points":[[0,0],[0,100],[-450,100],[-450,0]],"start":{"id":"ci"},"end":{"id":"idle"},"label":{"text":"3rd wrong PIN (retain)\n/ eject"}},
 {"type":"arrow","id":"auth-idle","x":1220,"y":150,"width":-930,"height":0,"points":[[0,0],[0,-100],[-930,-100],[-930,0]],"start":{"id":"auth"},"end":{"id":"idle"},"label":{"text":"eject / timeout"}},
 {"type":"arrow","id":"auth-oos","x":1220,"y":220,"width":1,"height":180,"start":{"id":"auth"},"end":{"id":"oos"},"label":{"text":"dispenser jam"}},
 {"type":"arrow","id":"oos-idle","x":1090,"y":435,"width":-850,"height":-215,"points":[[0,0],[-850,0],[-850,-215]],"start":{"id":"oos"},"end":{"id":"idle"},"label":{"text":"technician reset"}}
]}

Code

from __future__ import annotations
import threading, uuid
from dataclasses import dataclass
from enum import Enum
from typing import Protocol

class AtmState(Enum):
    IDLE, CARD_INSERTED, AUTHENTICATED, OUT_OF_SERVICE = range(4)

class AtmError(Exception): ...  # every refusal shown to the customer
@dataclass(frozen=True)
class Card:
    number: str
    account_id: str

class BankService(Protocol):
    def verify_pin(self, card: Card, pin: str) -> bool: ...
    def balance(self, account_id: str) -> int: ...
    def hold(self, account_id: str, amount: int, txn_id: str) -> bool: ...
    def commit(self, txn_id: str) -> None: ...
    def release(self, txn_id: str) -> None: ...  # idempotent
    def deposit(self, account_id: str, amount: int, txn_id: str) -> None: ...

class InMemoryBank:  # test double; production is a network client
    def __init__(self, pins: dict[str, str], balances: dict[str, int]) -> None:
        self.pins, self.bal = pins, balances
        self.holds: dict[str, tuple[str, int]] = {}
    def verify_pin(self, card: Card, pin: str) -> bool: return self.pins.get(card.number) == pin
    def balance(self, account_id: str) -> int: return self.bal[account_id]
    def commit(self, txn_id: str) -> None: self.holds.pop(txn_id)
    def deposit(self, account_id: str, amount: int, txn_id: str) -> None: self.bal[account_id] += amount
    def hold(self, account_id: str, amount: int, txn_id: str) -> bool:
        if self.bal[account_id] < amount:
            return False
        self.bal[account_id] -= amount  # available balance drops while held
        self.holds[txn_id] = (account_id, amount)
        return True
    def release(self, txn_id: str) -> None:
        if txn_id in self.holds:
            account_id, amount = self.holds.pop(txn_id)
            self.bal[account_id] += amount

class CashDispenser:  # owned by one ATM and only touched under its lock
    def __init__(self, cassettes: dict[int, int]) -> None:
        self.cassettes = dict(cassettes)  # denomination -> notes available
        self.jammed = False
    def reserve(self, amount: int) -> dict[int, int] | None:
        denoms = sorted(self.cassettes, reverse=True)
        def solve(i: int, rest: int) -> dict[int, int] | None:
            if rest == 0 or i == len(denoms):
                return {} if rest == 0 else None
            d = denoms[i]
            for n in range(min(rest // d, self.cassettes[d]), -1, -1):  # big notes first
                sub = solve(i + 1, rest - n * d)
                if sub is not None:
                    return {d: n, **sub} if n else sub
            return None
        notes = solve(0, amount)
        for d, n in (notes or {}).items():
            self.cassettes[d] -= n  # take the notes so nobody else can plan with them
        return notes
    def restock(self, notes: dict[int, int]) -> None:
        for d, n in notes.items():
            self.cassettes[d] += n
    def eject(self, notes: dict[int, int]) -> bool:
        return not self.jammed  # hardware reports whether every note left the slot

class ATM:
    MAX_PIN_TRIES = 3
    def __init__(self, bank: BankService, dispenser: CashDispenser) -> None:
        self.bank, self.dispenser = bank, dispenser
        self.state, self.tries = AtmState.IDLE, 0
        self.card: Card | None = None
        self.journal: list[str] = []
        self.reversals: list[str] = []  # store-and-forward: a job resends until the bank acks
        self.lock = threading.Lock()  # keypad, timer and hardware events serialise here
    def _require(self, *states: AtmState) -> Card:
        if self.state not in states or self.card is None:
            raise AtmError(f"not allowed in state {self.state.name}")
        return self.card
    def insert_card(self, card: Card) -> None:
        with self.lock:
            if self.state is not AtmState.IDLE:
                raise AtmError(f"not allowed in state {self.state.name}")
            self.state, self.card, self.tries = AtmState.CARD_INSERTED, card, 0
    def enter_pin(self, pin: str) -> bool:
        with self.lock:
            card = self._require(AtmState.CARD_INSERTED)
            if self.bank.verify_pin(card, pin):
                self.state = AtmState.AUTHENTICATED
                return True
            self.tries += 1
            if self.tries >= self.MAX_PIN_TRIES:
                self.journal.append(f"card {card.number} retained")
                self.state, self.card = AtmState.IDLE, None
            return False
    def balance(self) -> int:
        with self.lock:
            return self.bank.balance(self._require(AtmState.AUTHENTICATED).account_id)
    def withdraw(self, amount: int) -> dict[int, int]:
        with self.lock:
            account = self._require(AtmState.AUTHENTICATED).account_id
            notes = self.dispenser.reserve(amount) if amount > 0 else None
            if notes is None:
                raise AtmError("invalid amount or cannot make it with the notes on hand")
            txn = uuid.uuid4().hex
            try:
                approved: bool | None = self.bank.hold(account, amount, txn)
            except ConnectionError:
                approved = None
                self.reversals.append(txn)  # the hold may have landed
            if not approved:
                self.dispenser.restock(notes)
                raise AtmError("insufficient funds" if approved is False else "bank unavailable")
            if not self.dispenser.eject(notes):  # jam: notes stay quarantined
                self.reversals.append(txn)
                self.journal.append(f"{txn} jam, reversal queued, {notes} quarantined")
                self.state, self.card = AtmState.OUT_OF_SERVICE, None  # card returned
                raise AtmError("dispenser fault, transaction cancelled")
            self.bank.commit(txn)
            self.journal.append(f"{txn} withdraw {amount} as {notes}")
            return notes
    def deposit(self, amount: int) -> None:
        with self.lock:
            account = self._require(AtmState.AUTHENTICATED).account_id
            if amount <= 0:
                raise AtmError("amount must be positive")
            self.bank.deposit(account, amount, uuid.uuid4().hex)
            self.journal.append(f"deposit {amount}")  # bank credits it as pending
    def eject_card(self) -> None:
        with self.lock:
            self._require(AtmState.CARD_INSERTED, AtmState.AUTHENTICATED)
            self.state, self.card = AtmState.IDLE, None

atm = ATM(InMemoryBank({"4111": "1234"}, {"acc-1": 500}), CashDispenser({50: 2, 20: 10}))
atm.insert_card(Card("4111", "acc-1"))
assert not atm.enter_pin("0000") and atm.enter_pin("1234")
print(atm.withdraw(60))  # {20: 3}: greedy would take a 50 and strand 10
atm.deposit(100); print(atm.balance())  # 540
atm.eject_card()

release is idempotent, so a background job can resend every queued reversal until the bank acknowledges it. One lock on ATM serialises keypad input, the session timer and hardware callbacks; the dispenser is only touched under it.

Design patterns

  • State — AtmState plus _require guards every operation. With more states (maintenance, transaction in progress) this becomes one State class per state, and ATM delegates each event to the current state object.
  • Dependency inversion — ATM depends on the BankService interface, so a network client or InMemoryBank plugs in unchanged.
  • Two-phase commit (hold / commit / release) — keeps the account and the cash in step across a hardware step that can fail.
  • Facade — ATM is the single entry point the screen and keypad talk to.

Extensions

  • Transfers, mini-statements: new ATM methods guarded by AUTHENTICATED and new BankService calls; the state machine does not change.
  • Daily withdrawal limit: enforced by the bank inside hold, since only the bank sees every ATM.
  • Note-mix policy: extract the search in reserve into a NoteMixStrategy (fewest notes vs. spend denominations with the most stock) — a Strategy.
  • Crash recovery: persist each journal entry with txn_id and phase before the next step. On restart, a hold with no COMMITTED or RELEASED and no confirmed eject is reversed; a confirmed eject is committed.

Interviewer expectations

Mid-level (L4)

  • Clear classes for ATM, card, bank, dispenser, and a state enum.
  • PIN-attempt limit and state checks before every operation.
  • A working note-mix algorithm, and knows pure greedy can fail.

Senior (L5)

  • Two-phase withdrawal: reserve notes, hold, dispense, commit; every failure undoes the earlier steps.
  • Bank behind an interface; idempotent transaction ids; refusals vs. hardware faults.
  • Thread safety across keypad, timer and hardware events.

Staff (L6+)

  • Handles ambiguous outcomes (timeout after a hold may have landed) with store-and-forward reversals and reconciliation.
  • Persistent journal, crash recovery, quarantined notes and cassette reconciliation.
  • Puts limits and fraud in the bank and cash inventory and sessions in the ATM; explains when to move from an enum to the State pattern.

Sign in to comment, vote or remix.