In-Memory Banking System with Scheduled Payments and Account Merges

Design and implement a single-threaded, in-memory banking system that supports scheduled payments, account merges, and time-travel balance queries.

APIs and Semantics

1. transfer(timestamp, source_account_id, target_account_id, amount) -> str | None

   • At timestamp, deduct amount from the source account’s available balance and freeze it.
   • Funds remain frozen until the target accepts or the transfer expires exactly 24 hours after initiation.
   • On expiry, funds automatically return to the source, and the transfer can no longer be accepted.
   • Return None if:
     • source_account_id equals target_account_id.
     • Either account does not exist at timestamp.
     • The source has insufficient available balance (excluding already frozen funds).
   • On success, return a unique transfer ID (e.g., "transfer1", "transfer2").
   • Frozen funds contribute to both parties’ pending (unsettled) totals and do not enter either account’s transaction history until accepted.

2. accept_transfer(timestamp, account_id, transfer_id) -> bool

   • Return True if and only if:
     • The transfer exists.
     • The transfer is not expired.
     • The transfer is not already accepted or cancelled.
     • account_id is exactly the transfer’s current target at timestamp.
   • Otherwise, return False.

3. merge_accounts(timestamp, account_id_1, account_id_2) -> bool

   • At timestamp, merge account_id_2 into account_id_1.
   • Return False if:
     • account_id_1 equals account_id_2.
     • Either account does not exist at timestamp.
   • If successful:
     • Cancel all pending transfers originating from account_id_2.
     • Cancel all pending transfers from account_id_1 to account_id_2.
     • Redirect all other pending inbound transfers whose target is account_id_2 so their target becomes account_id_1.
     • Increase account_id_1 balance by account_id_2 balance.
     • Aggregate both accounts’ historical totals as combined.
     • Delete account_id_2.
     • Return True.

4. get_balance(timestamp, account_id, time_at) -> int | None

   • Return the balance of account_id immediately after processing all operations at time_at.
   • Return None if the account did not yet exist by time_at or had been deleted by then.
   • Otherwise, return the correct historical balance.

Constraints

• Amounts and balances are integers.
• Timestamps are integer units; 24 hours is exactly 24 * 60 * 60 units after initiation.
• Acceptance at or after the expiry moment is invalid.
• Operations may arrive in any timestamp order; you must answer historical queries correctly for arbitrary time_at.

Expectations

• Describe data structures/algorithms (e.g., hash maps, event log/ledger, min-heap or timer wheel for expirations, indices for per-account state, and any persistence-like strategy for time travel), their time/space complexity, and how to generate unique IDs.
• Provide a working single-threaded in-memory implementation and justify design choices.
• Briefly discuss how you would extend to handle concurrency and scale.

Minimal Assumptions to Make the Problem Self-Contained

• Accounts are created outside the four required APIs (e.g., via a helper create_account(account_id, created_at, initial_balance)). The four required APIs must still enforce existence checks at their timestamps.
• "Balance" means settled ledger balance (excludes frozen funds). "Available" means balance minus currently frozen outgoing amounts.
• Event ordering at the same timestamp will be deterministic: Initiations first, then Merges, then Accepts, then Expirations.