In-Memory Bank System With Top-N Activity Ranking and Expiring Pending Transfers

Implement an in-memory banking system as a single class. The task is delivered in stages: each stage adds behavior to the same class, and everything from earlier stages must keep working unchanged. Every operation receives an integer `timestamp` as its first argument. Assume a class shaped like this (names are illustrative; keep the semantics): ```python class Bank: def __init__(self, transfer_window: int): ... def create_account(self, timestamp: int, account_id: str) -> bool: ... def deposit(self, timestamp: int, account_id: str, amount: int) -> int | None: ... def pay(self, timestamp: int, account_id: str, amount: int) -> int | None: ... def top_activity(self, timestamp: int, n: int) -> list[tuple[str, int]]: ... def transfer(self, timestamp: int, source_id: str, target_id: str, amount: int) -> str | None: ... def accept_transfer(self, timestamp: int, account_id: str, transfer_id: str) -> bool: ... ``` ### Constraints and Clarifications - Timestamps are integers and strictly increase from one call to the next. - Amounts are positive integers; a balance may never go negative. - Account ids are non-empty strings. - `transfer_window` is a positive integer fixed when the bank is created; the length of the acceptance window was not specified, so treat it as a parameter. - A failed operation changes no state. ### Clarifying Questions - Should invalid calls (unknown account, insufficient funds) return a failure value or raise? This version returns `None` or `False`. - Can an account be deleted or renamed? (Assume not.) - Are timestamps guaranteed strictly increasing, or must the class tolerate out-of-order calls? (Assume strictly increasing.) ### Part 1 — Accounts, deposits and payments Implement: - `create_account`: creates an account with balance 0; returns `False` if the id already exists. - `deposit`: adds `amount` to the account and returns the new balance; returns `None` if the account does not exist. - `pay`: withdraws `amount` and returns the new balance; returns `None` if the account does not exist or its balance is smaller than `amount`. ```hint Validate before mutating Settle every failure condition of `pay` before touching any balance, so a rejected payment leaves no trace that a later stage could trip over. ``` #### What This Part Should Cover - An account registry keyed by id, with duplicate-creation handling - Rejection of unknown accounts and overdrafts without partial state changes - Return values that later stages can build on ### Part 2 — Activity statistics and top n Every successful `deposit` and `pay` counts toward its account's activity. Implement `top_activity(timestamp, n)`, which returns up to `n` accounts with the highest activity, highest first, as `(account_id, activity)` pairs. ```hint Where the numbers live Ask whether this query should replay every past transaction or read something that `deposit` and `pay` already keep up to date. ``` #### Clarifying Questions for this Part - Is activity the total amount deposited plus paid, the amount paid only, or the number of transactions? - How are accounts with equal activity ordered? - What should be returned when `n` exceeds the number of accounts? - Do rejected deposits or payments count? #### What This Part Should Cover - Incremental aggregation versus recomputation at query time - A deterministic order with an explicit tie-break - Cost of updates versus queries, and which structure fits which query rate ### Part 3 — Transfers with a hold, acceptance, and expiry Implement transfers between two accounts: - `transfer(timestamp, source_id, target_id, amount)` immediately deducts `amount` from the source account (the money is held) but does **not** credit the target. It returns a new unique transfer id, or `None` if either account does not exist, the two ids are the same, or the source balance is smaller than `amount`. - `accept_transfer(timestamp, account_id, transfer_id)` credits the target account only if the transfer exists, is still pending, `account_id` is its target, and acceptance happens within `transfer_window` of the moment the transfer was created. It returns `True` on success and `False` otherwise. - A pending transfer that is not accepted within the window expires, and the held amount returns to the source account. ```hint Give the transfer a lifecycle Write down the states a transfer can be in and which calls may move it from one state to another; every legal transition should happen exactly once. ``` ```hint Nobody calls you at the deadline No method is invoked at the exact moment a transfer expires. Decide which calls must first account for everything that expired since the previous call. ``` #### Clarifying Questions for this Part - Is an acceptance at exactly `created_at + transfer_window` still valid? - Can the sender cancel a pending transfer? - Should transfers, or refunds of expired transfers, count toward the activity statistic from Part 2? #### What This Part Should Cover - Hold semantics: held money is unavailable to `pay` and to other transfers, and is never credited twice - When and in what order expirations are applied, and that each refund happens exactly once - Validation of acceptance: unknown id, wrong account, already accepted, already expired - Data structures for pending transfers and their per-operation cost ### What a Strong Answer Covers - Each stage extends the class without rewriting earlier logic - A stated money invariant (balances plus held amounts always equal total deposits minus total payments) and code that preserves it - Concrete test sequences: pay against held funds, accept after expiry, accept by the wrong account, ties in the ranking - Time and space cost per operation ### Follow-up Questions - Let the sender cancel a pending transfer. What new state does that add, and how do cancellation and expiry interact? - With millions of pending transfers, how do you keep expiry handling from making an unrelated `deposit` slow? - If `top_activity` had to answer "as of" an earlier timestamp, what would you need to store? - If calls could arrive out of timestamp order, which parts of your design break first?