Bank ledger with two-step transfers and merges

Question: Bank ledger with two-step transfers and merges

Companies: Anthropic

Difficulty: Medium

Problem statement

Model simple bank accounts with deposits and withdrawals, a transfer flow that holds funds until the recipient accepts, and an account-merge step that must keep working even if a merged account is later recreated.

• Level 1: create_account(ts, id), deposit(ts, id, amount), withdraw(ts, id, amount); deposit and withdraw return the new balance or None.
• Level 2: transfer(ts, src, dst, amount) holds the money and returns "transfer1", ...; accept_transfer(ts, dst, transfer_id) must happen within 24 hours (86_400_000 ms), or the money goes back.
• Level 3: merge_accounts(ts, keep, gone): balances and pending transfers move to keep; gone can be created again later and must not receive the old account's transfers.

DAY_MS = 86_400_000


class Bank:
    def create_account(self, ts, account_id): ...
    def deposit(self, ts, account_id, amount): ...
    def withdraw(self, ts, account_id, amount): ...

    def transfer(self, ts, src_id, dst_id, amount): ...
    def accept_transfer(self, ts, account_id, transfer_id): ...

    def merge_accounts(self, ts, keep_id, gone_id): ...

Approach

The spec used here (timestamps are milliseconds and only grow; failed calls return None or False):

Clarify first. Is the hold visible in the sender's balance (yes: the balance drops at transfer time)? Can you transfer to yourself (no)? Does an expired transfer refund at the moment of expiry, even if nobody calls anything (we only need the observable result to be right, so we settle lazily at the next call)? What if the sender was merged before the transfer expires (the refund goes to the account that absorbed it)?

The key decision: separate an account's identity from its id string. The Level 3 trap is "merge, then recreate the id". If transfers store the string "bob", the new "bob" can accept money meant for the old one. Store a reference to an Account object instead. Each create_account makes a new object, so a recreated id is a different account by construction. A merge then repoints the pending transfers that referenced the gone object.

Lazy expiry. Keep a min-heap of (expires_at, transfer_id). Every public method first calls _settle(ts), which pops due transfers that are still pending and refunds them. Because timestamps only grow, settling before each call gives the same answers as a real timer. Entries for transfers that were already accepted are skipped when popped.

Invariant (worth stating, and testing). Total money = sum of balances + sum of pending holds. Deposits add to it, withdrawals subtract, and nothing else changes it: not transfers, accepts, refunds or merges.

Code

import heapq
from itertools import count

DAY_MS = 86_400_000


class Account:
    def __init__(self, account_id):
        self.id = account_id
        self.balance = 0


class Transfer:
    def __init__(self, src, dst, amount, expires_at):
        self.src, self.dst, self.amount, self.expires_at = src, dst, amount, expires_at
        self.status = "pending"  # pending | accepted | expired | cancelled


class Bank:
    def __init__(self):
        self.accounts = {}      # id -> Account (live accounts only)
        self.transfers = {}     # transfer id -> Transfer
        self.expiry = []        # heap of (expires_at, seq, transfer id)
        self._seq = count(1)

    # -- helpers -----------------------------------------------------------
    def _settle(self, ts):
        while self.expiry and self.expiry[0][0] <= ts:
            _, _, tid = heapq.heappop(self.expiry)
            t = self.transfers[tid]
            if t.status == "pending":
                t.status = "expired"
                t.src.balance += t.amount

    def _live(self, account_id):
        return self.accounts.get(account_id)

    # -- level 1 -----------------------------------------------------------
    def create_account(self, ts, account_id):
        self._settle(ts)
        if account_id in self.accounts:
            return False
        self.accounts[account_id] = Account(account_id)
        return True

    def deposit(self, ts, account_id, amount):
        self._settle(ts)
        acct = self._live(account_id)
        if acct is None or amount <= 0:
            return None
        acct.balance += amount
        return acct.balance

    def withdraw(self, ts, account_id, amount):
        self._settle(ts)
        acct = self._live(account_id)
        if acct is None or amount <= 0 or acct.balance < amount:
            return None
        acct.balance -= amount
        return acct.balance

    # -- level 2 -----------------------------------------------------------
    def transfer(self, ts, src_id, dst_id, amount):
        self._settle(ts)
        src, dst = self._live(src_id), self._live(dst_id)
        if src is None or dst is None or src is dst or amount <= 0 or src.balance < amount:
            return None
        src.balance -= amount  # hold
        seq = next(self._seq)
        tid = f"transfer{seq}"
        self.transfers[tid] = Transfer(src, dst, amount, ts + DAY_MS)
        heapq.heappush(self.expiry, (ts + DAY_MS, seq, tid))
        return tid

    def accept_transfer(self, ts, account_id, transfer_id):
        self._settle(ts)
        t = self.transfers.get(transfer_id)
        acct = self._live(account_id)
        if t is None or acct is None or t.status != "pending" or t.dst is not acct:
            return False
        t.status = "accepted"
        acct.balance += t.amount
        return True

    # -- level 3 -----------------------------------------------------------
    def merge_accounts(self, ts, keep_id, gone_id):
        self._settle(ts)
        keep, gone = self._live(keep_id), self._live(gone_id)
        if keep is None or gone is None or keep is gone:
            return False
        keep.balance += gone.balance
        for t in self.transfers.values():
            if t.status != "pending":
                continue
            ends = {t.src, t.dst}
            if ends == {keep, gone}:
                t.status = "cancelled"
                keep.balance += t.amount  # the refund lands in keep whichever side sent it
                continue
            if t.src is gone:
                t.src = keep
            if t.dst is gone:
                t.dst = keep
        del self.accounts[gone_id]
        return True

In the cancelled case the refund goes straight to keep: whether keep or gone sent it, both are now the same account, and gone's balance was already folded in, so refunding to gone would lose the money.

Complexity

Space is O(A + T): accounts, transfers and heap entries.

Test cases

from solution import Bank


def test_create_deposit_withdraw():
    b = Bank()
    assert b.create_account(1, "ana") is True
    assert b.create_account(2, "ana") is False
    assert b.deposit(3, "ana", 100) == 100
    assert b.withdraw(4, "ana", 30) == 70
    assert b.withdraw(5, "ana", 71) is None
    assert b.deposit(6, "zed", 5) is None

from solution import DAY_MS, Bank


def setup():
    b = Bank()
    b.create_account(1, "ana")
    b.create_account(2, "bob")
    b.deposit(3, "ana", 100)
    return b


def test_transfer_holds_then_accept_credits():
    b = setup()
    assert b.transfer(10, "ana", "bob", 40) == "transfer1"
    assert b.withdraw(12, "ana", 61) is None        # only 60 available
    assert b.accept_transfer(13, "ana", "transfer1") is False  # not the recipient
    assert b.accept_transfer(14, "bob", "transfer1") is True
    assert b.accept_transfer(15, "bob", "transfer1") is False  # only once
    assert b.withdraw(16, "bob", 40) == 0


def test_expiry_refunds_at_exactly_24_hours():
    b = setup()
    b.transfer(10, "ana", "bob", 40)
    assert b.accept_transfer(10 + DAY_MS, "bob", "transfer1") is False
    assert b.withdraw(10 + DAY_MS, "ana", 100) == 0


def test_accept_just_before_expiry():
    b = setup()
    b.transfer(10, "ana", "bob", 40)
    assert b.accept_transfer(10 + DAY_MS - 1, "bob", "transfer1") is True


def test_invalid_transfers():
    b = setup()
    assert b.transfer(10, "ana", "ana", 1) is None
    assert b.transfer(11, "ana", "zed", 1) is None
    assert b.transfer(12, "ana", "bob", 101) is None

from solution import DAY_MS, Bank


def setup():
    b = Bank()
    for i, name in enumerate(["ana", "bob", "cy"]):
        b.create_account(i, name)
        b.deposit(10 + i, name, 100)
    return b


def test_merge_moves_balance_and_redirects_incoming():
    b = setup()
    b.transfer(20, "cy", "bob", 30)
    assert b.merge_accounts(21, "ana", "bob") is True
    assert b.withdraw(22, "ana", 200) == 0
    assert b.accept_transfer(23, "ana", "transfer1") is True
    assert b.withdraw(24, "ana", 30) == 0


def test_recreated_id_cannot_take_old_transfers():
    b = setup()
    b.transfer(20, "cy", "bob", 30)
    b.merge_accounts(21, "ana", "bob")
    assert b.create_account(22, "bob") is True
    assert b.accept_transfer(23, "bob", "transfer1") is False
    assert b.deposit(24, "bob", 1) == 1


def test_outgoing_hold_refunds_to_the_keeper():
    b = setup()
    b.transfer(20, "bob", "cy", 30)
    b.merge_accounts(21, "ana", "bob")       # ana has 100 + 70
    assert b.withdraw(20 + DAY_MS, "ana", 200) == 0  # refund of 30 landed first


def test_transfer_between_merged_accounts_is_cancelled():
    b = setup()
    b.transfer(20, "ana", "bob", 30)
    b.merge_accounts(21, "ana", "bob")
    assert b.accept_transfer(22, "ana", "transfer1") is False
    assert b.withdraw(23, "ana", 200) == 0


def test_merge_rejects_bad_ids():
    b = setup()
    assert b.merge_accounts(20, "ana", "ana") is False
    assert b.merge_accounts(21, "ana", "zed") is False

Follow-ups

1. Historical balances. Record (ts, balance) on every change through one _set_balance helper, then binary-search for "balance at time t". Keep the history on the Account object so a recreated id starts a new history rather than continuing the old one.
2. Pending index. The merge scan is O(all transfers). Keep account.pending: set[transfer id] updated on transfer, accept, expiry and cancel, and merge in O(pending of the gone account).
3. Real ledgers. Replace mutable balances with append-only double-entry postings: a hold is a posting from the account to a "holds" account, accept moves it from holds to the recipient, expiry moves it back. Balances are sums. The money invariant becomes "every entry has a matching opposite entry", which auditors can check.
4. Concurrency. Lock both accounts in a fixed order (by internal uid) for transfers and merges to avoid deadlock. Expiry run by a background worker needs the same locks and an idempotent status change (pending -> expired only if still pending).
5. Idempotency. Network retries can send transfer twice. Accept a client-supplied idempotency key and return the original transfer id on a repeat.

Interviewer expectations

Mid-level (L4)

• Gets Level 1 and the hold/accept flow right, including "only the recipient can accept" and "accept once".
• Implements expiry with the correct boundary (expired at exactly 24 hours).
• Tests the failure cases (unknown account, insufficient funds, self-transfer).

Senior (L5)

• Settles expiry lazily with a heap and explains why it matches a real timer when timestamps grow.
• Separates account identity from the id string, so a recreated id cannot take the old account's transfers.
• Handles all merge cases: incoming, outgoing, and a pending transfer between the two accounts.

Staff (L6+)

• States the conservation invariant and uses it to check every operation.
• Moves toward double-entry postings, idempotency keys and lock ordering without being asked, while keeping the timed solution simple.
• Leaves the code structured so a fourth level (history, fees, scheduled payments) is an addition, not a rewrite.