Katkat

Implement a Time-Aware Banking System

AirbnbSoftware Engineer · Online Assessment

Last updated

Design and implement a stateful, time-aware in-memory banking ledger that handles atomic transfers, deferred/scheduled executions, account mergers, historical balance queries, and activity rankings.

Problem Statement

Implement an in-memory banking system that processes operations sequentially under a monotonically increasing timestamp. The system must process pending scheduled transfers up to the current timestamp before executing any new operation.

Implement the BankSystem class with the following methods:

  • create_account(timestamp: int, account_id: str) -> bool: Creates an account with a balance of 0. Returns True if created successfully, or False if account_id already exists.
  • deposit(timestamp: int, account_id: str, amount: int) -> int | None: Adds amount to account_id. Returns the new balance, or None if the account does not exist.
  • transfer(timestamp: int, from_id: str, to_id: str, amount: int) -> bool: Immediately transfers amount from from_id to to_id. Both accounts must exist, from_id != to_id, and from_id must have balance >= amount. Returns True on success, False otherwise.
  • schedule_transfer(timestamp: int, scheduled_time: int, transfer_id: str, from_id: str, to_id: str, amount: int) -> bool: Schedules a transfer at scheduled_time. Returns False if scheduled_time bool: Cancels a pending scheduled transfer. Returns True if successfully cancelled, or False if transfer_id does not exist or has already executed.
  • merge_accounts(timestamp: int, target_id: str, source_id: str) -> bool: Merges source_id into target_id. Moves the remaining balance of source_id to target_id, rebinds all pending scheduled transfers involving source_id to target_id, and deactivates source_id. Both accounts must exist and target_id != source_id. Returns True on success, False otherwise.
  • get_balance(timestamp: int, account_id: str, as_of_time: int) -> int | None: Returns the account balance exactly at as_of_time (as_of_time list[str]: Returns the top n accounts by total outbound transfer volume (including direct and scheduled transfers, excluding deposits and balance merges). Tie-break accounts alphabetically.

Execution Rules

  1. Across all API calls, timestamp is non-decreasing.
  2. Before any operation at timestamp executes, all scheduled transfers where scheduled_time <= timestamp must execute in chronological order. Break ties by transfer_id lexicographically.
  3. If an account has insufficient funds at the scheduled execution time, the transfer fails silently and is discarded.

Example

bank = BankSystem()
bank.create_account(1, "A")          # True
bank.create_account(1, "B")          # True
bank.deposit(2, "A", 100)            # 100
bank.schedule_transfer(3, 10, "t1", "A", "B", 40) # True
bank.get_balance(5, "A", 4)          # 100 (balance at t=4)
bank.get_balance(11, "A", 10)        # 60 (t1 executed at t=10)
bank.get_top_spenders(12, 1)         # ["A"]

Constraints

  • All timestamp and scheduled_time are integers where 1 0.
  • At most 20,000 total method calls.

Hints

Hint 1

Maintain a min-heap of pending scheduled transfers ordered by `(scheduled_time, transfer_id)` and process due items before every method call.

Hint 2

Record every balance-mutating event with its timestamp per account so historical balances can be retrieved via binary search (bisection).

Hint 3

When merging accounts, remember to update pending transfers in the heap or use an indirection mapping (pointer/alias) so rebinding does not require rebuilding the heap.

Follow-up questions

  • How would you optimize `merge_accounts` if accounts have thousands of pending transfers?
  • If timestamps could arrive out of order from distributed clients, how would you redesign the settlement boundary and conflict resolution?
  • How would you support recurring scheduled payments (e.g., cron or interval-based) without creating an unbounded number of future records?