ATM
medium · transactions, fault tolerance, rollback
Brief-reported interview attribution (unverified): Amazon, Microsoft
How to approach an LLD roundRequirements
- Functional: check balance, deposit and withdraw with PIN authentication; dispense cash in denominations; a failed dispense must roll the debit back; deposits add cash to the machine (must be valid multiples of 10 so cash inventory stays reconciled).
- Non-functional: a withdrawal is a transaction — it must never debit without dispensing; cash inventory must stay consistent; production PIN protection is required but out of scope here: this educational in-memory reference stores plain-text test PINs and must not handle real credentials.
- Out of scope: card reading, network/bank integration, receipts, multi-currency.
Statement
Design an ATM. It holds accounts (account_id → balance in cents
and a PIN) and a cash inventory by denomination (100, 50, 20, 10). The
core rule: **a withdrawal is a transaction — the account is debited only if the
cash is actually dispensed. If dispensing fails, the debit is rolled back.** For
testability the ATM has a fault-injection method fail_next_dispense() that makes
the next dispense fail (in production this is the hardware error).
class ATM:
def __init__(self, accounts, cash):
# accounts: {account_id: {"balance": int, "pin": str}}; cash: {denom: count}
def balance(self, account_id, pin):
# -> balance, or None for a wrong PIN / unknown account
def deposit(self, account_id, amount):
# -> new balance, or None for an unknown account / amount <= 0 / non-multiple of 10
# (deposited cash is added to the inventory, largest denominations first)
def withdraw(self, account_id, pin, amount):
# -> ("ok", {denom: count}) or ("error", reason)
# reasons: "wrong pin", "invalid amount", "insufficient funds",
# "cannot dispense", "dispense failed"
def fail_next_dispense(self):
# test hook: the next withdraw attempt fails at the dispense step
def cash_on_hand(self):
# -> total cash in the machineRules. Withdrawal checks, in order: PIN, amount > 0 and a multiple of 10,
balance ≥ amount, the amount can be formed from the denominations, and the
inventory actually holds those notes (greedy, largest first). Only then is the
account debited; if the dispense fails, the debit is rolled back and the error is
"dispense failed". deposit checks amount > 0 and amount % 10 == 0 so the deposited cash decomposes cleanly into denominations without losing remainder cents, then adds the amount to the balance and to the cash inventory.
Money units: account balances, deposits, withdrawals and denominations are integer cents. Denomination 100 means 100 cents.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Account (balance + PIN check; SRP). CashDispenser (inventory, note selection, dispense; SRP). Withdrawal (the debit → dispense → rollback unit; SRP — the transaction boundary). ATM orchestrates and takes the dispenser as a constructor argument (DIP). Pattern: Transaction (withdrawal as an atomic unit).
Optional constructor collaborators: dispenser and withdrawal_factory; defaults retain the specified API behavior.
Public demo
# Public demo: run after implementing the class API above.
a = ATM({'A1': {'balance': 500, 'pin': '1234'}}, {100: 5, 50: 5, 20: 5, 10: 5})
print(a.balance('A1', '1234'))
print(a.balance('A1', '0000'))
print(a.balance('ZZ', '1234'))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two withdrawals at once must not dispense the same cash. The debit + dispense pair must be atomic: hold one lock per account for the balance change and one lock on the dispenser for the cash, taken in the same order every time (account, then dispenser) so two withdrawals cannot deadlock. The reference is single-threaded; the locks are described here.
Trade-offs & extensions
Greedy selection minimizes notes with unlimited cash in these denominations, but limited inventory can make it reject an amount that a different combination could dispense. This exercise preserves the specified greedy selection and inventory check; supporting every feasible limited-inventory combination would require a bounded search. Extending: add a Card/BankService boundary with idempotency keys so the ATM talks to a bank interface instead of local accounts, and a TransactionLog for audit.
Starter code
class Account:
def __init__(self, balance, pin):
"""accounts: {account_id: {"balance": int, "pin": str}}; cash: {denom: count}"""
pass
def check_pin(self, pin):
"""Implement the return value and rules in the API contract."""
pass
def debit(self, amount):
"""Implement the return value and rules in the API contract."""
pass
def credit(self, amount):
"""Implement the return value and rules in the API contract."""
pass
class CashDispenser:
def __init__(self, cash):
"""accounts: {account_id: {"balance": int, "pin": str}}; cash: {denom: count}"""
pass
def fail_next_dispense(self):
"""test hook: the next withdraw attempt fails at the dispense step"""
pass
def notes_for(self, amount):
"""Implement the return value and rules in the API contract."""
pass
def can_dispense(self, notes):
"""Implement the return value and rules in the API contract."""
pass
def dispense(self, notes):
"""Implement the return value and rules in the API contract."""
pass
def add_cash(self, amount):
"""Implement the return value and rules in the API contract."""
pass
def total(self):
"""Implement the return value and rules in the API contract."""
pass
class Withdrawal:
def __init__(self, account, dispenser, amount):
"""accounts: {account_id: {"balance": int, "pin": str}}; cash: {denom: count}"""
pass
def execute(self):
"""Implement the return value and rules in the API contract."""
pass
class ATM:
def __init__(self, accounts, cash, dispenser=None, withdrawal_factory=None):
"""accounts: {account_id: {"balance": int, "pin": str}}; cash: {denom: count}"""
pass
def fail_next_dispense(self):
"""test hook: the next withdraw attempt fails at the dispense step"""
pass
def balance(self, account_id, pin):
"""-> balance, or None for a wrong PIN / unknown account"""
pass
def deposit(self, account_id, amount):
"""-> new balance, or None for an unknown account / amount <= 0 / non-multiple of 10 (deposited cash is added to the inventory, largest denominations first)"""
pass
def withdraw(self, account_id, pin, amount):
'''-> ("ok", {denom: count}) or ("error", reason) reasons: "wrong pin", "invalid amount", "insufficient funds", "cannot dispense", "dispense failed"'''
pass
def cash_on_hand(self):
"""-> total cash in the machine"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter