Banking system with transfers, cashback and account merges

Clarify first. This is a multi-level design problem: each level adds methods, and the earlier ones must keep passing. Ask before writing code. Are amounts positive integers? What does a failed call return (None here)? Does a payment count as "outgoing" for the spender ranking (yes)? How are ties ranked (outgoing descending, then account id ascending)? Is cashback rounded down (yes, 2% floored)? Do timestamps strictly increase across calls (yes)?

Data model. Keep one dictionary accounts: id -> Account(balance, outgoing, payments). Send every balance change through one helper, _set_balance, which also appends (timestamp, balance) to that id's history. Level 1 does not need the history, but routing writes through one place means Level 4 adds no new write paths.

Level 1 (create, deposit, transfer). These are plain dictionary operations. A transfer fails when either account is missing, when the source and target are the same, or when the source balance is too low. It returns the source's new balance.

Level 2 (top spenders). Keep a running outgoing total on each account. Transfers out and payments both add to it. Brute force is the right answer: sort all accounts by (-outgoing, id) and format the first n as id(total). That costs O(A log A) per query. If the interviewer pushes on it, a heap of size n gives O(A log n).

Level 3 (payments with delayed cashback). pay withdraws now, gives the payment a global id (payment1, payment2, ...), and schedules 2% cashback 24 hours later (86,400,000 ms). Do not use a timer. Every public method first calls _settle(ts), which pops all cashbacks due at or before ts from a min-heap keyed by due time and credits them. Cashback due at exactly ts lands before the operation at ts runs. Because calls arrive in time order, lazy settlement gives the same result as a real clock. get_payment_status returns IN_PROGRESS or CASHBACK_RECEIVED, or None when the payment does not belong to that account.

Level 4 (merge, historical balance). merge_accounts(keep, gone) adds the gone account's balance and outgoing total to the kept account. It moves the gone account's payments to the kept account, so pending cashback now lands there, then deletes the gone account. get_balance(ts, id, time_at) binary-searches that id's history for the last entry at or before time_at. A merge appends None to the deleted id's history, and a time before the first entry also gives None. So a query on a deleted account before the merge still returns its old balance, and a query after the merge returns None.

Invariants.

• Each account's balance equals the last value in its history.
• Every history list is sorted by time. This holds because _settle credits cashback at its due time, in due order, before the current call writes anything at a later time.
• Each payment has exactly one owner, and that owner is a live account.

import heapq
from bisect import bisect_right
from dataclasses import dataclass, field
from typing import Optional

CASHBACK_DELAY = 86_400_000  # 24 hours in milliseconds
CASHBACK_PERCENT = 2


@dataclass
class Account:
    balance: int = 0
    outgoing: int = 0
    payments: set[str] = field(default_factory=set)


@dataclass
class Payment:
    owner: str
    cashback: int
    done: bool = False


class BankingSystem:
    def __init__(self) -> None:
        self.accounts: dict[str, Account] = {}
        self.payments: dict[str, Payment] = {}
        self.pending: list[tuple[int, int, str]] = []  # (due, seq, payment id)
        self.seq = 0
        # Balance history per id: parallel lists; None means "no account".
        self.hist_t: dict[str, list[int]] = {}
        self.hist_v: dict[str, list[Optional[int]]] = {}

    # ---- helpers -------------------------------------------------------
    def _record(self, ts: int, acct_id: str, value: Optional[int]) -> None:
        self.hist_t.setdefault(acct_id, []).append(ts)
        self.hist_v.setdefault(acct_id, []).append(value)

    def _set_balance(self, ts: int, acct_id: str, delta: int) -> int:
        acct = self.accounts[acct_id]
        acct.balance += delta
        self._record(ts, acct_id, acct.balance)
        return acct.balance

    def _settle(self, ts: int) -> None:
        """Credit every cashback due at or before ts, in due order."""
        while self.pending and self.pending[0][0] <= ts:
            due, _, pid = heapq.heappop(self.pending)
            p = self.payments[pid]
            self._set_balance(due, p.owner, p.cashback)
            p.done = True

    # ---- Level 1 -------------------------------------------------------
    def create_account(self, ts: int, acct_id: str) -> bool:
        self._settle(ts)
        if acct_id in self.accounts:
            return False
        self.accounts[acct_id] = Account()
        self._record(ts, acct_id, 0)
        return True

    def deposit(self, ts: int, acct_id: str, amount: int) -> Optional[int]:
        self._settle(ts)
        if acct_id not in self.accounts:
            return None
        return self._set_balance(ts, acct_id, amount)

    def transfer(self, ts: int, src: str, dst: str, amount: int) -> Optional[int]:
        self._settle(ts)
        if src == dst or src not in self.accounts or dst not in self.accounts:
            return None
        if self.accounts[src].balance < amount:
            return None
        self.accounts[src].outgoing += amount
        self._set_balance(ts, dst, amount)
        return self._set_balance(ts, src, -amount)

    # ---- Level 2 -------------------------------------------------------
    def top_spenders(self, ts: int, n: int) -> list[str]:
        self._settle(ts)
        ranked = sorted(self.accounts.items(), key=lambda kv: (-kv[1].outgoing, kv[0]))
        return [f"{aid}({a.outgoing})" for aid, a in ranked[:n]]

    # ---- Level 3 -------------------------------------------------------
    def pay(self, ts: int, acct_id: str, amount: int) -> Optional[str]:
        self._settle(ts)
        acct = self.accounts.get(acct_id)
        if acct is None or acct.balance < amount:
            return None
        acct.outgoing += amount
        self._set_balance(ts, acct_id, -amount)
        self.seq += 1
        pid = f"payment{self.seq}"
        self.payments[pid] = Payment(acct_id, amount * CASHBACK_PERCENT // 100)
        acct.payments.add(pid)
        heapq.heappush(self.pending, (ts + CASHBACK_DELAY, self.seq, pid))
        return pid

    def get_payment_status(self, ts: int, acct_id: str, pid: str) -> Optional[str]:
        self._settle(ts)
        acct = self.accounts.get(acct_id)
        if acct is None or pid not in acct.payments:
            return None
        return "CASHBACK_RECEIVED" if self.payments[pid].done else "IN_PROGRESS"

    # ---- Level 4 -------------------------------------------------------
    def merge_accounts(self, ts: int, keep: str, gone: str) -> bool:
        self._settle(ts)
        if keep == gone or keep not in self.accounts or gone not in self.accounts:
            return False
        a, b = self.accounts[keep], self.accounts.pop(gone)
        a.outgoing += b.outgoing
        for pid in b.payments:  # pending cashback now lands in `keep`
            self.payments[pid].owner = keep
        a.payments |= b.payments
        self._set_balance(ts, keep, b.balance)
        self._record(ts, gone, None)
        return True

    def get_balance(self, ts: int, acct_id: str, time_at: int) -> Optional[int]:
        self._settle(ts)
        times = self.hist_t.get(acct_id)
        if not times:
            return None
        i = bisect_right(times, time_at)
        return self.hist_v[acct_id][i - 1] if i else None

Let A be the number of accounts, P the number of payments, and H the length of one account's history.

Space is O(A + P + total history entries). There is one history entry per balance change.

• create_account(1, "ana") gives True. Calling it again for "ana" gives False.
• deposit(4, "ana", 500) gives 500. deposit(5, "zed", 10) gives None (no such account).
• After "ben" is created, transfer(6, "ana", "ben", 200) gives 300 (ana's new balance).
• transfer(7, "ana", "ana", 1) gives None (same account). transfer(8, "ben", "ana", 999) gives None (not enough money).
• top_spenders(9, 5) gives ["ana(200)", "ben(0)"]. Accounts with zero outgoing still count, with ties broken by id.
• pay(10, "ana", 100) gives "payment1", and ana's balance drops to 200. At time 12 the status is IN_PROGRESS. Asking for the same payment on "ben" gives None.
• At time 10 + 86_400_000, cashback of 2 lands before the call, so deposit(..., "ana", 0) gives 202 and the status is CASHBACK_RECEIVED.
• Cashback rounds down: a payment of 49 earns 0, and a payment of 50 earns 1.
• Merge with pending cashback: ben pays 50 (balance 150, cashback 1 pending), then merge_accounts(t, "ana", "ben") gives True. Ana's balance becomes 352. A day after ben's payment it becomes 353, and get_payment_status(..., "ana", "payment2") reports it.
• merge_accounts a second time, or with the same id twice, gives False.
• get_balance(now, "ben", t_before_merge) gives ben's old balance (150). At the merge time or later it gives None. get_balance(now, "ana", 0) gives None because ana did not exist yet.

1. Re-creating a merged id. After a merge, can "ben" be created again? With this design it can. Creation appends (ts, 0) to the same history list, so historical queries still answer correctly on both sides of the gap.
2. Withdrawals and scheduled transfers. A scheduled transfer is another heap event, like cashback. Settle it at its due time, and decide what happens when the balance is too low at that moment (usually it fails silently and gets a FAILED status). Keep one event heap with typed events instead of one heap per feature.
3. Top spenders at scale. Many accounts and frequent queries make the full sort too slow. Keep a sorted structure keyed by (-outgoing, id), such as sortedcontainers.SortedList. Each update is a remove plus an insert in O(log A), and a query is O(n).
4. Transaction history and audits. Store immutable transaction records (type, amount, counterparty, timestamp) in place of bare balance snapshots. Balances then become a derived view, and a merge does not have to rewrite ownership: it records a merge event. This is how a real ledger works (double-entry, append-only).
5. Concurrency and durability. If calls are concurrent, use a lock per account, always taken in id order to avoid deadlock on transfers. Use a write-ahead log so a crash cannot apply a debit without the matching credit. Cashback settlement becomes a background worker with idempotent payment ids.

Mid-level (L4)

• Gets Levels 1 and 2 right quickly, including every failure case (missing account, same account, not enough money).
• Implements cashback correctly at the 24-hour boundary, with flooring.
• Writes small tests against the given examples and moves on without getting stuck.

Senior (L5)

• Picks a data model on Level 1 that makes Levels 3 and 4 additions, not rewrites (one write path, history recorded from the start).
• Uses lazy settlement with a min-heap and explains why it is correct given increasing timestamps.
• Handles the merge edge cases: pending cashback moves to the kept account, payment ownership moves, and the deleted account's history stays queryable.

Staff (L6+)

• States the invariants (history sorted, balance equals the last history value, one live owner per payment) and shows which helper keeps each one.
• Discusses the move to an append-only ledger, idempotency, and per-account locking without being prompted, and is clear about which parts are out of scope for a timed assessment.
• Manages time across all four levels and leaves the code readable enough for someone else to extend with a fifth.