Design and implement a bank account system

### Reading the problem This is a classic "leveled" CodeSignal-style task (the kind HubSpot uses): you implement one class that grows across 3-4 levels, and each level adds a capability on top of the previous one. The grader runs unit tests, so **correctness and exact method contracts matter more than cleverness**. The winning strategy is: - Keep state in plain in-memory data structures (no DB — it's a single process). - Make every operation small, total (always returns or raises predictably), and easy to test. - Treat money as **integer minor units (cents)**, never floats. - Add a single lock so the "safe under concurrent requests" requirement is satisfied without you having to reason about per-account locking. I'll build it in the same order the levels appear, then give complexity and edge cases. --- ### Core design decisions | Decision | Choice | Why | |---|---|---| | Money representation | `int` cents | Floats lose precision (`0.1 + 0.2 != 0.3`); banking cannot tolerate that. The validator below enforces `int` strictly. | | Account storage | `dict[account_id -> Account]` | O(1) lookup/insert; account IDs are unique keys. | | Per-account history | `list[Transaction]` appended in order | History is append-only and naturally time-ordered; "last N" is a slice. | | Transfers | `dict[transfer_id -> Transfer]` with a status enum | Transfers are first-class entities with their own lifecycle, independent of accounts. | | Concurrency | One coarse-grained `threading.RLock` (the "bank lock") | Simplest correct answer; eliminates lost-update/double-spend races. Re-entrant so methods can call each other. | | Time | Inject a `clock` callable (defaults to `time.time`) | Makes expiry testable and avoids depending on wall-clock in tests. | A coarse lock is the right call in an interview: per-account locks introduce deadlock ordering problems (account A locks B while B locks A). Mention the trade-off; don't implement it unless asked. --- ### Level 1 — Accounts, deposit, withdraw, overdraft protection ```python import threading import itertools import time from enum import Enum from dataclasses import dataclass, field class OpType(str, Enum): DEPOSIT = "deposit" WITHDRAWAL = "withdrawal" TRANSFER_PENDING = "transfer_pending" # debit-intent recorded when transfer is created TRANSFER_OUT = "transfer_out" # sender side, on accept TRANSFER_IN = "transfer_in" # recipient side, on accept @dataclass class Transaction: timestamp: float op_type: OpType amount: int # cents, always positive resulting_balance: int # account balance AFTER this op @dataclass class Account: account_id: str balance: int # cents history: list = field(default_factory=list) class Bank: def __init__(self, clock=time.time): self._accounts: dict[str, Account] = {} self._lock = threading.RLock() self._clock = clock # ---- helpers ------------------------------------------------- def _require_account(self, account_id: str) -> Account: acct = self._accounts.get(account_id) if acct is None: raise KeyError(f"account {account_id!r} does not exist") return acct @staticmethod def _require_positive(amount: int) -> None: # bool is a subclass of int, so reject it explicitly: deposit(acct, True) # is a programming error, not a 1-cent deposit. if not isinstance(amount, int) or isinstance(amount, bool): raise TypeError("amount must be an integer number of cents") if amount <= 0: raise ValueError("amount must be positive") def _record(self, acct: Account, op: OpType, amount: int) -> None: acct.history.append(Transaction(self._clock(), op, amount, acct.balance)) # ---- Level 1 API --------------------------------------------- def create_account(self, account_id: str, initial_balance: int = 0) -> str: with self._lock: if account_id in self._accounts: raise ValueError(f"account {account_id!r} already exists") if initial_balance < 0: raise ValueError("initial balance cannot be negative") self._accounts[account_id] = Account(account_id, initial_balance) return account_id def deposit(self, account_id: str, amount: int) -> int: self._require_positive(amount) with self._lock: acct = self._require_account(account_id) acct.balance += amount self._record(acct, OpType.DEPOSIT, amount) return acct.balance def withdraw(self, account_id: str, amount: int) -> int: self._require_positive(amount) with self._lock: acct = self._require_account(account_id) if acct.balance < amount: raise ValueError("insufficient funds") # overdraft prevented acct.balance -= amount self._record(acct, OpType.WITHDRAWAL, amount) return acct.balance def get_balance(self, account_id: str) -> int: with self._lock: return self._require_account(account_id).balance ``` Key points the graders check at this level: deposit/withdraw return the new balance, withdrawing more than the balance is rejected (no overdraft), and negative/zero amounts raise. Doing validation **before** taking the lock is fine for stateless checks; the balance check must be **inside** the lock so it reflects the committed state. --- ### Level 2 — Transaction history History is already being appended on every mutation via `_record`. We just expose two read APIs: ```python def get_history(self, account_id: str) -> list: with self._lock: # return a shallow copy so callers can't mutate internal state return list(self._require_account(account_id).history) def get_recent_history(self, account_id: str, n: int) -> list: if n < 0: raise ValueError("n must be non-negative") with self._lock: return list(self._require_account(account_id).history[-n:]) if n else [] ``` Each record carries `timestamp`, `op_type`, `amount`, and `resulting_balance`, matching the spec exactly. Because we append in operation order, the list is already chronological — `[-n:]` gives the most recent `n` without sorting. The `if n else []` guard is load-bearing: `list[-0:]` is `list[0:]`, which returns the *whole* list, so `n == 0` must be special-cased to return an empty slice. Returning a copy prevents callers from corrupting history. --- ### Level 3 — Two-phase transfers with explicit accept This is the level that fails most candidates because of the lifecycle and idempotency. Model a transfer as a small state machine: ``` PENDING ──accept──► ACCEPTED │ ├──reject──► REJECTED └──expire──► EXPIRED ``` Once a transfer leaves PENDING it is **terminal** — further accept/reject calls must be idempotent (return the same outcome, never double-apply). **Critical design question: do we hold funds at creation or only check at acceptance?** The spec says "validate sufficient funds at acceptance time," so I do **not** debit the sender on `create_transfer` — I only validate and move money on `accept`. The `transfer_pending` history entry records intent without changing balances. (If the prompt instead wanted an escrow hold, you'd debit on create and refund on reject/expire; call this out to the interviewer.) ```python class TransferStatus(str, Enum): PENDING = "pending" ACCEPTED = "accepted" REJECTED = "rejected" EXPIRED = "expired" @dataclass class Transfer: transfer_id: str from_id: str to_id: str amount: int created_at: float expires_at: float | None status: TransferStatus = TransferStatus.PENDING ``` Add to `Bank.__init__`: ```python self._transfers: dict[str, Transfer] = {} self._transfer_seq = itertools.count(1) # monotonic id generator ``` Methods: ```python def create_transfer(self, from_id, to_id, amount, ttl_seconds=None) -> str: self._require_positive(amount) with self._lock: sender = self._require_account(from_id) recipient = self._require_account(to_id) # validate recipient now if from_id == to_id: raise ValueError("cannot transfer to the same account") now = self._clock() tid = f"t{next(self._transfer_seq)}" self._transfers[tid] = Transfer( transfer_id=tid, from_id=from_id, to_id=to_id, amount=amount, created_at=now, expires_at=(now + ttl_seconds) if ttl_seconds is not None else None, ) # record intent on the sender, without moving money self._record(sender, OpType.TRANSFER_PENDING, amount) return tid def _resolve_if_expired(self, t: Transfer) -> None: """Lazily expire on read/write — no background timer needed.""" if (t.status is TransferStatus.PENDING and t.expires_at is not None and self._clock() >= t.expires_at): t.status = TransferStatus.EXPIRED def accept_transfer(self, transfer_id: str) -> TransferStatus: with self._lock: t = self._transfers.get(transfer_id) if t is None: raise KeyError("unknown transfer") self._resolve_if_expired(t) # ---- idempotency: terminal states are returned unchanged ---- if t.status is TransferStatus.ACCEPTED: return t.status # duplicate accept: no double-credit if t.status in (TransferStatus.REJECTED, TransferStatus.EXPIRED): return t.status # cannot accept a dead transfer sender = self._accounts[t.from_id] recipient = self._accounts[t.to_id] if sender.balance < t.amount: # funds checked AT ACCEPT TIME raise ValueError("insufficient funds at acceptance") sender.balance -= t.amount recipient.balance += t.amount self._record(sender, OpType.TRANSFER_OUT, t.amount) self._record(recipient, OpType.TRANSFER_IN, t.amount) t.status = TransferStatus.ACCEPTED return t.status def reject_transfer(self, transfer_id: str) -> TransferStatus: with self._lock: t = self._transfers.get(transfer_id) if t is None: raise KeyError("unknown transfer") self._resolve_if_expired(t) if t.status is TransferStatus.PENDING: t.status = TransferStatus.REJECTED # ACCEPTED stays ACCEPTED; REJECTED/EXPIRED are already terminal return t.status def get_transfer_status(self, transfer_id: str) -> TransferStatus: with self._lock: t = self._transfers.get(transfer_id) if t is None: raise KeyError("unknown transfer") self._resolve_if_expired(t) return t.status ``` **Why this is idempotent and concurrency-safe:** - The status check and the balance mutation happen **atomically inside one lock acquisition**. Two threads calling `accept_transfer` on the same id can't both pass the `status is PENDING` gate — the first flips it to `ACCEPTED`, the second sees `ACCEPTED` and returns without re-crediting. - The same holds for accept-vs-reject races: whichever grabs the lock first sets the terminal state; the loser observes it and no-ops. - Expiry is **lazy** (checked on every read/write) rather than via a background thread, which keeps the system deterministic and avoids timer/race complexity. It's also exactly what tests want: advance the injected clock, then assert the transfer is `EXPIRED`. A small, deliberate design choice worth stating: on `reject`/`expire` I do **not** append a compensating "cancel" record to the sender's history, so a reader of `get_history` still sees the original `transfer_pending` intent for a transfer that never moved money. Balances and every `resulting_balance` stay correct (nothing was debited), and the spec only mandates the five listed op-types — but if the grader expects pending intents to be visibly retracted, I'd add a `transfer_cancelled` op-type and write it in `reject_transfer` and `_resolve_if_expired`. --- ### Complexity Let $h$ = history length of the relevant account. | Operation | Time | Space | |---|---|---| | `create_account` | $O(1)$ | $O(1)$ | | `deposit` / `withdraw` | $O(1)$ | $O(1)$ per appended record | | `get_history` | $O(h)$ (copy) | $O(h)$ | | `get_recent_history(n)` | $O(n)$ | $O(n)$ | | `create_transfer` | $O(1)$ | $O(1)$ | | `accept` / `reject` / status | $O(1)$ | $O(1)$ | Total space is $O(A + T + H)$ for $A$ accounts, $T$ transfers, and $H$ total history records. `get_history` returns a copy for safety; if that copy cost matters, return a read-only view or a paginated slice instead. --- ### Edge cases (call these out explicitly — graders test them) - **Duplicate requests / idempotency.** Re-accepting an accepted transfer returns `ACCEPTED` without double-crediting; re-rejecting returns the existing terminal status. Account creation with an existing id raises rather than silently overwriting. - **Invalid accounts.** Every account-touching call routes through `_require_account`, raising `KeyError` for missing accounts — including the recipient at transfer-creation time. - **Negative / zero / non-integer amounts.** `_require_positive` rejects all of these uniformly, and rejects `bool` explicitly (since `True`/`False` are `int` instances) so `deposit(acct, True)` is a type error rather than a 1-cent deposit. `create_account` separately rejects a negative initial balance. - **Overdraft.** Withdraw and accept both verify `balance >= amount` inside the lock against committed state; a transfer that was fundable at creation can still be rejected at accept time if the sender drained the account in between — which is exactly why funds are validated at acceptance, not creation. - **Self-transfer.** Rejected explicitly at `create_transfer`: it's a no-op move that produces confusing duplicate history (a `transfer_pending`, then on accept a `transfer_out` and `transfer_in` on the same account that net to zero), so it's cleaner to forbid it outright. (Under the coarse global lock shown here it can't deadlock; the deadlock concern only arises in the per-account-locking design discussed above, which is one more reason that design is harder to get right.) - **Clock / timestamp considerations.** Time is injected, so tests are deterministic and don't flake on wall-clock. Expiry uses `>=` so a transfer is dead exactly at `expires_at`. Don't assume monotonic timestamps from `time.time` (NTP can step it backwards) — if strict ordering matters, pair each record with a monotonic sequence counter, since history order here comes from append order, not from comparing timestamps. - **Concurrency.** The single re-entrant lock makes every mutation a critical section, so no lost updates, no double-spend, no partial transfer where one side is credited but the other isn't. --- ### What I'd say out loud in the interview > "I'm storing money as integer cents to avoid float errors, keeping accounts and transfers in dicts for O(1) access, and appending to a per-account history list so 'last N' is just a slice. Transfers are a small state machine — PENDING to one of three terminal states — and I get idempotency and concurrency safety from a single coarse lock plus the rule that terminal states are never re-applied. I validate funds at *acceptance* time per the spec, and I expire lazily off an injected clock so the behavior is testable. If you want higher concurrency I'd move to per-account locks with a global ordering to avoid deadlocks, or push this into a transactional store — but for a single-process service the coarse lock is correct and simple." That sequencing — minimal correct core, then explicit trade-offs — is what separates a pass from a fail on this problem.