Design a bank system with scheduled transfers

Bank System (OOD): Accounts, Transfers, Scheduling, Top Spending, Merge

Design an in-memory banking system that supports:

• account creation
• deposits/withdrawals
• immediate transfers
• scheduled (delayed) transfers with cancellation
• querying top spenders
• merging accounts

Core rules

• Each account has a balance (integer, starts at 0).
• Each operation is called with a timestamp.
• Before executing any operation at time t, the system must process all scheduled transfers whose execution time <= t.
• “Spending” for a customer is the total money sent out (withdrawals + transfers out, including scheduled transfers once executed; depending on your interpretation, you may also count scheduled transfers as spending when reserved—state your choice and be consistent).

API

1. create_account(timestamp, customer_id) -> bool

   • Create if not exists.

2. deposit(timestamp, customer_id, amount) -> bool

   • Fail if account doesn’t exist.

3. withdraw(timestamp, customer_id, amount) -> bool

   • Fail if account doesn’t exist or insufficient funds.
   • Counts toward spending.

4. transfer(timestamp, from_id, to_id, amount) -> bool

   • Immediate transfer.
   • Fail if either account missing or insufficient funds.
   • Counts amount toward from_id spending.

5. top_spending(timestamp, n) -> list<string>

   • Return top n customers formatted "customerId(total)".
   • Sort by total spending desc, then customerId asc.

6. schedule_transfer(timestamp, from_id, to_id, amount, delay) -> string | null

   • Create a transfer that will execute at timestamp + delay.
   • If invalid (missing accounts or insufficient funds), return null.
   • Return a unique transfer_id for cancellation.
   • Funds may be “reserved” immediately or deducted at execution; choose one and document it.

7. cancel_transfer(timestamp, customer_id, transfer_id) -> bool

   • Cancel only if:
     • transfer_id exists
     • status is still pending (not executed)
     • the customer_id is the sender
   • Return whether cancellation succeeded.

8. merge_account(timestamp, from_id, to_id) -> bool

   • Merge from_id into to_id:
     • Move remaining balance into to_id
     • Add spending totals
     • Update any pending scheduled transfers that reference from_id as sender or receiver to reference to_id
     • Delete from_id

Notes

• Assume up to ~1e5 operations.
• You may use a min-heap/priority queue for scheduled transfers.

Design a Bank System with Scheduled Transfers

Implement an in-memory banking simulator.

Write solution(operations) that processes the operations in order and returns a list of results, one per operation.

Each operation is a tuple or list whose first element is the operation name:

• ('create_account', timestamp, customer_id) -> bool
• ('deposit', timestamp, customer_id, amount) -> bool
• ('withdraw', timestamp, customer_id, amount) -> bool
• ('transfer', timestamp, from_id, to_id, amount) -> bool
• ('top_spending', timestamp, n) -> list[str]
• ('schedule_transfer', timestamp, from_id, to_id, amount, delay) -> str | None
• ('cancel_transfer', timestamp, customer_id, transfer_id) -> bool
• ('merge_account', timestamp, from_id, to_id) -> bool

Rules:

• Every account starts with balance 0.
• Before executing any operation at time t, first execute all pending scheduled transfers with execution time <= t.
• This problem uses reservation semantics for scheduled transfers: when a scheduled transfer is created successfully, its amount is removed from the sender immediately.
• If a pending scheduled transfer is canceled, that reserved amount is refunded to the sender's current live account.
• A scheduled transfer increases spending only when it actually executes.
• If merges cause a pending scheduled transfer's sender and receiver to become the same live account, execution simply returns the reserved money to that account and does not increase spending.
• top_spending considers only current live accounts and returns at most n strings formatted as "customerId(total)", sorted by total spending descending, then customer_id ascending.
• Successful scheduled transfers must return deterministic IDs: 'transfer1', 'transfer2', ... in order of successful scheduling.
• A merged-away ID is deleted and cannot be created again.

Return the result of every operation in order.

Constraints

• 1 <= len(operations) <= 10^5
• Timestamps are integers in non-decreasing order.
• customer_id, from_id, and to_id are non-empty strings and IDs are never reused after creation.
• Amounts are positive integers; delay and n are non-negative integers.

Examples

Example 1

Input: [('create_account', 1, 'alice'), ('create_account', 1, 'bob'), ('deposit', 2, 'alice', 100), ('transfer', 3, 'alice', 'bob', 30), ('withdraw', 4, 'bob', 10), ('top_spending', 5, 2)]
Output: [True, True, True, True, True, ['alice(30)', 'bob(10)']]

Explanation: Alice sends 30 to Bob, and Bob withdraws 10. Spending totals are Alice=30 and Bob=10.

Example 2

Input: [('create_account', 1, 'ann'), ('create_account', 1, 'ben'), ('deposit', 2, 'ann', 50), ('schedule_transfer', 3, 'ann', 'ben', 20, 5), ('top_spending', 4, 2), ('cancel_transfer', 7, 'ann', 'transfer1'), ('top_spending', 9, 2)]
Output: [True, True, True, 'transfer1', ['ann(0)', 'ben(0)'], True, ['ann(0)', 'ben(0)']]

Explanation: The scheduled transfer reserves 20 immediately, but spending stays 0 until execution. It is canceled before time 8, so the money is refunded and no spending is added.

Hints

1. A min-heap keyed by execution time is a natural way to process all scheduled transfers due before the current operation.
2. Do not scan every pending transfer during merge_account. Instead, keep a mapping from old IDs to current live IDs and resolve them lazily when a scheduled transfer executes or is canceled.

Approach

The solution keeps live-account state in three dicts — balances, spending, and version — and processes operations in order.

Time-ordered scheduling. A min-heap scheduled_heap holds (exec_time, seq, transfer_id). At the start of every op, process_due(timestamp) pops all transfers due at <= t and settles them before the current op runs, satisfying the "execute pending first" rule.

Reservation semantics. On schedule_transfer, if the sender can afford it, the amount is debited immediately and a pending record is stored. cancel_transfer refunds the reserved amount to the sender's current live account and marks it canceled. Settlement only counts spending when sender and receiver are distinct live accounts.

Merges via union-find. merge_account folds from_id into to_id (summing balances/spending), deletes the source from all dicts, and sets parent[from_id] = to_id. find (with path compression) resolves any old ID to its live owner. When a scheduled transfer executes, find re-resolves both endpoints; if they collapse to the same account, the money is simply returned with no spending — matching the spec.

top_spending via a lazy heap. Each spending change pushes (-total, id, version) onto spend_heap and bumps version[id]. A query pops entries, skipping any whose id is dead, whose version is stale, or whose stored total no longer matches — guaranteeing the popped entry reflects current state. Popped survivors are collected and pushed back. The (-total, id) ordering gives descending spend, ties broken by ascending id.

Determinism comes from next_transfer_num (transfer IDs) and schedule_seq (heap tie-break), so equal-time transfers settle in scheduling order.

• Space complexity: O(q) — the dicts hold at most one entry per account, and both heaps plus the transfers map grow at most linearly in the number of operations.