Courses › Low-Level Design › Problem Walkthroughs

Design an ATM & Digital Wallet

Atomic transfers, idempotency keys, double-entry ledgers, ATM states and dispensing cash.

ATMs, digital wallets and in-memory banks are the "money" family of LLD questions. They share three requirements interviewers care about: money is never created or lost, operations are atomic (a transfer moves money completely or not at all), and retries are safe (a duplicated request doesn't charge twice). The ATM adds a state machine for the session and a cash dispenser problem.

Part 1: the account core (wallet / bank)

Requirements

  • Accounts with balances. Deposit, withdraw, and transfer between accounts.
  • Withdrawals and transfers can't overdraw an account.
  • Every change is recorded in a transaction history.
  • A request repeated with the same idempotency key is applied only once.
  • Safe under concurrent requests.

Model

Account          id, balance (cents), lock
LedgerEntry      txn_id, account_id, amount (+/-), kind, timestamp
WalletService    accounts, ledger, processed[idempotency_key] -> result
                 deposit, withdraw, transfer(src, dst, amount, key)

[!TIP] Double-entry thinking Record a transfer as two ledger entries that cancel out (−X on the source, +X on the destination), under one transaction ID. The sum of all entries for a transfer is always zero, so money can't appear or vanish. Balances can always be rebuilt from the ledger. That's how real financial systems work, and saying so earns credit.

Implementation

import threading
import uuid
from dataclasses import dataclass


class InsufficientFunds(Exception):
    pass


@dataclass
class Account:
    id: str
    balance: int = 0                     # cents

    def __post_init__(self):
        self.lock = threading.Lock()


class WalletService:
    def __init__(self):
        self.accounts = {}
        self.ledger = []                 # (txn_id, account_id, amount, kind)
        self.processed = {}              # idempotency key -> txn_id
        self._idem_lock = threading.Lock()

    def open(self, account_id):
        self.accounts[account_id] = Account(account_id)

    def _once(self, key, action):
        """Run `action` at most once per idempotency key."""
        with self._idem_lock:
            if key in self.processed:
                return self.processed[key]
            self.processed[key] = None   # reserve the key (a real system would store "in progress")
        try:
            txn_id = action()
        except Exception:
            with self._idem_lock:
                del self.processed[key]  # allow a retry after a failure
            raise
        with self._idem_lock:
            self.processed[key] = txn_id
        return txn_id

    def deposit(self, account_id, amount, key):
        if amount <= 0:
            raise ValueError("amount must be positive")
        def action():
            acct = self.accounts[account_id]
            with acct.lock:
                acct.balance += amount
                txn = str(uuid.uuid4())
                self.ledger.append((txn, account_id, amount, "deposit"))
                return txn
        return self._once(key, action)

    def transfer(self, src_id, dst_id, amount, key):
        if amount <= 0 or src_id == dst_id:
            raise ValueError("invalid transfer")
        def action():
            src, dst = self.accounts[src_id], self.accounts[dst_id]
            first, second = sorted((src, dst), key=lambda a: a.id)   # fixed lock order
            with first.lock, second.lock:
                if src.balance < amount:
                    raise InsufficientFunds(src_id)
                src.balance -= amount
                dst.balance += amount
                txn = str(uuid.uuid4())
                self.ledger.append((txn, src_id, -amount, "transfer"))
                self.ledger.append((txn, dst_id, amount, "transfer"))
                return txn
        return self._once(key, action)
w = WalletService()
w.open("ana"); w.open("bo")
w.deposit("ana", 10_000, key="dep-1")
t1 = w.transfer("ana", "bo", 2_500, key="xfer-42")
t2 = w.transfer("ana", "bo", 2_500, key="xfer-42")      # client retry: not applied twice
assert t1 == t2 and w.accounts["ana"].balance == 7_500 and w.accounts["bo"].balance == 2_500
assert sum(amount for _, _, amount, kind in w.ledger if kind == "transfer") == 0

Points to raise:

  • Lock ordering prevents deadlock when two transfers go in opposite directions at the same time.
  • Check, then mutate, under the same lock. Checking the balance outside the lock is a race condition.
  • Idempotency: this version holds the key reserved while the action runs. A concurrent duplicate sees None, meaning "in progress". In a real system it would wait or return a conflict. Mention that, rather than pretending it can't happen.

Part 2: the ATM

Requirements

  • Insert a card, enter a PIN (locked after 3 failed attempts), choose an operation: balance, withdraw, or deposit.
  • The withdrawal is checked against the account and against the cash available in the machine.
  • Dispense notes using the available denominations.
  • Eject the card at the end, or on cancel or timeout.

Session state machine

(Idle) -> [card inserted] -> (Card inserted) -> [PIN ok] -> (Authenticated) -> [select withdraw] -> (Dispensing) -> [done] -> (Idle)
(Card inserted) -> [3 wrong PINs] -> [retain card] -> (Idle)
(Authenticated) -> [cancel / timeout] -> [eject card] -> (Idle)

Model each state as a class with insert_card, enter_pin, withdraw and cancel, exactly as in Design a Vending Machine. The ATM talks to the bank through a BankService interface: authenticate(card, pin), debit(account, amount, key), credit(...).

Dispensing cash

With standard denominations (100, 50, 20, 10), greedy usually works, but not always when some notes have run out. Asking for 60 with only 50s and 20s fails greedily (50, then 10 is left over), while 20 × 3 works. A small bounded search fixes it:

def dispense(amount, notes):            # notes: {denomination: count}
    denoms = sorted(notes, reverse=True)
    def go(i, remaining):
        if remaining == 0:
            return {}
        if i == len(denoms):
            return None
        d = denoms[i]
        for use in range(min(notes[d], remaining // d), -1, -1):
            rest = go(i + 1, remaining - use * d)
            if rest is not None:
                return {d: use, **rest} if use else rest
        return None
    return go(0, amount)

dispense(60, {50: 1, 20: 5}) returns {20: 3}.

Order of operations

This is where most candidates slip. The order matters when anything can fail:

  • Check that the machine can dispense the amount, before debiting.
  • Debit the account with an idempotency key tied to this ATM transaction.
  • Dispense the cash.
  • If dispensing fails (a hardware jam), reverse the debit with a compensating credit, and log it for reconciliation.

[!INTERVIEW] What if the ATM loses its connection after the debit? The ATM retries the debit with the same idempotency key, so the bank never charges twice. If it can't confirm, it doesn't dispense, and a reconciliation process settles it later. Every money question has a version of this follow-up. Answering it with idempotency plus compensation is the expected answer.

[!TIP] Practice Design an ATM · Design a Digital Wallet · In-Memory Banking System · Keeping Money Correct