Bank Account System

Note on Reconstruction

This is a reconstructed interview-style problem inspired by known bank-account / time-series coding questions from large tech companies. It is not the exact proprietary Airbnb prompt, but it closely matches the intended title, tags (Object-Oriented Design, Data Structures, Time Series), and difficulty.

---

Problem Description

You are asked to design and implement an in-memory Bank Account System that processes a stream of time-stamped commands.

The system must:

• Maintain bank accounts identified by string IDs, each with a non-negative integer balance.
• Support real-time operations such as creating accounts, depositing funds, transferring funds, querying balances, and computing top spenders.
• Support time-based operations:
  • Scheduling future payments between accounts at specified timestamps.
  • Canceling previously scheduled payments.
  • Merging one account into another and handling all related scheduled payments consistently.

Commands arrive with non-decreasing timestamps. Before processing each new command at time t, the system must automatically execute all scheduled payments whose executeAt time is ≤ t and have not yet been executed or canceled.

Transfers (including scheduled payments) count toward each account’s total outgoing transfer volume, which is used to answer TOP_SPENDERS queries.

The goal is to implement the core processing logic so that, given a list of time-stamped commands, the system returns the outputs for query-type commands in order.

---

Input/Output Format

Assume you implement a function with the following abstract signature (adapt to your language of choice):

text processEvents(events: List<List<string>>) -> List<string>

• events[i] is a list of tokens (all provided as strings).

• Each events[i] has this general form:

  text [timestamp, commandName, arg1, arg2, ...]

• timestamp is an integer in string form, and the sequence of timestamps is non-decreasing.

• The function returns a list of strings, each corresponding to the result of a query-type command, in the same order those queries appear.

Supported Commands

All numeric arguments (timestamps, amounts, k) are non-negative integers given as strings. accountId and paymentId are non-empty strings without spaces.

1. CREATE

   text [t, "CREATE", accountId, initialBalance]

   • If accountId does not yet exist, create it with balance = initialBalance.
   • If accountId already exists, treat this as an invalid command and ignore it (no output).

2. DEPOSIT

   text [t, "DEPOSIT", accountId, amount]

   • If accountId exists, increase its balance by amount.
   • If accountId does not exist, ignore the command (no output).

3. TRANSFER

   text [t, "TRANSFER", fromId, toId, amount]

   • If both fromId and toId exist and fromId has at least amount balance:
     • Decrease fromId’s balance by amount.
     • Increase toId’s balance by amount.
     • Increase fromId’s outgoing transfer total by amount.
   • Otherwise (missing account or insufficient funds), ignore the command.

4. BALANCE (query)

   text [t, "BALANCE", accountId]

   • If accountId exists, append its current balance (as a decimal string) to the output list.
   • Otherwise, append "ERROR" to the output list.

5. TOP_SPENDERS (query)

   text [t, "TOP_SPENDERS", k]

   • Consider all accounts that have sent any positive total outgoing transfer volume (via TRANSFER or executed scheduled payments).
   • Sort them primarily by total outgoing transfer volume in descending order, and break ties by accountId in lexicographical ascending order.
   • Take the top k such accounts (or fewer if fewer exist).
   • Append a single string to the output list: the selected accountIds joined by a single comma (,), with no spaces.
   • If no account has sent any transfers yet, append an empty string "".

6. SCHEDULE_PAYMENT

   text [t, "SCHEDULE_PAYMENT", paymentId, fromId, toId, amount, executeAt]

   • This creates a future payment with unique identifier paymentId:

     • At time executeAt, the system will attempt to transfer amount from fromId to toId.

   • Requirements:

     • paymentId must be unique among all scheduled payments. If it was already used, ignore this command.
     • If either fromId or toId does not exist at scheduling time, ignore this command.

   • Scheduled payments are not executed immediately; they are executed automatically when time advances:

     • Before processing any command at time t, execute all scheduled payments with executeAt ≤ t that are not already executed or canceled.

   • Execution rules:

     • If, at execution time, both accounts still exist and fromId has at least amount, perform the transfer and count it toward fromId’s outgoing transfer total.
     • If accounts are missing or funds are insufficient at execution time, the scheduled payment is skipped and marked executed (it is not retried).

   • SCHEDULE_PAYMENT itself produces no direct output.

7. CANCEL_PAYMENT

   text [t, "CANCEL_PAYMENT", paymentId]

   • If a scheduled payment with paymentId exists and has not yet executed or been canceled, mark it as canceled so it will never be executed.
   • If paymentId does not exist or has already executed or been canceled, ignore this command.
   • Produces no output.

8. MERGE

   text [t, "MERGE", targetId, sourceId]

   • Merge account sourceId into targetId:
     • If either account does not exist or they are the same ID, ignore this command.
     • Add sourceId’s balance to targetId’s balance.
     • Conceptually close sourceId:
       • After the merge, sourceId is considered deleted and cannot be referenced in future CREATE, DEPOSIT, TRANSFER, BALANCE, or MERGE commands.
     • For all pending scheduled payments involving sourceId:
       • If fromId == sourceId, change fromId to targetId.
       • If toId == sourceId, change toId to targetId.
       • (A payment where both fromId and toId are sourceId becomes a payment from targetId to targetId.)
   • Existing outgoing-transfer totals for both accounts are not merged; they remain associated with their original accountIds. Closed accounts can still appear in TOP_SPENDERS results if they previously sent transfers.
   • Produces no output.

Time Progression and Scheduled Payment Execution

• Events are processed in the order given.
• Let currentTime start at negative infinity (or simply “no time”).
• For each event with timestamp t:
  1. Set currentTime = t.
  2. Execute all scheduled payments with executeAt ≤ currentTime, in deterministic order:
     • First by executeAt ascending, then by paymentId lexicographically ascending (or any consistent rule).
  3. Process the current event at currentTime.

The only commands that append to the output are BALANCE and TOP_SPENDERS.

---

Examples

Example 1: Basic Operations and Transfers

Input:

text events = [ ["1", "CREATE", "A", "100"], ["2", "CREATE", "B", "50"], ["3", "TRANSFER", "A", "B", "30"], ["4", "BALANCE", "A"], ["5", "BALANCE", "B"], ["6", "TOP_SPENDERS", "2"] ]

Output:

text ["70", "80", "A,B"]

Explanation:

1. At t=1, create account A with balance 100.
2. At t=2, create account B with balance 50.
3. At t=3, TRANSFER A B 30:
   • A has enough funds.
   • A balance becomes 70; B balance becomes 80.
   • A’s outgoing transfer total becomes 30.
4. At t=4, BALANCE A → append "70".
5. At t=5, BALANCE B → append "80".
6. At t=6, TOP_SPENDERS 2:
   • A has sent 30; B has sent 0.
   • Sorted by outgoing volume desc → [A, B] (only A has positive volume, but B doesn’t count as a spender).
   • Only accounts with positive outgoing volume participate, so the list of spenders is [A].
   • However, since k=2, we take up to 2 spenders: only A exists, so the output is "A".

If you prefer to include accounts with zero outgoing volume, the problem statement would specify that; in this reconstruction, only accounts with strictly positive outgoing transfer volume are considered spenders.
(The sample output above assumes only positive-volume spenders. A stricter sample could be ["70", "80", "A"].)

For clarity: in this reconstructed spec, the correct final output for this example is ["70", "80", "A"].

---

Example 2: Scheduled Payments, Cancellation, and Merge

Input:

text events = [ ["1", "CREATE", "A", "100"], ["2", "CREATE", "B", "0"], ["3", "CREATE", "C", "50"], ["4", "SCHEDULE_PAYMENT", "p1", "A", "B", "40", "10"], ["5", "SCHEDULE_PAYMENT", "p2", "C", "A", "20", "8"], ["6", "BALANCE", "A"], ["7", "CANCEL_PAYMENT", "p1"], ["8", "BALANCE", "A"], ["9", "MERGE", "A", "C"], ["10", "BALANCE", "A"], ["11", "TOP_SPENDERS", "3"] ]

Step-by-step processing:

• Initial state: no accounts, no scheduled payments.

1. t=1: CREATE A 100

   • A balance = 100.

2. t=2: CREATE B 0

   • B balance = 0.

3. t=3: CREATE C 50

   • C balance = 50.

4. t=4: Execute all scheduled payments with executeAt ≤ 4

   • None yet.
     Process SCHEDULE_PAYMENT p1 A B 40 10:
   • p1 scheduled from A to B for amount 40 at executeAt=10.

5. t=5: Execute all with executeAt ≤ 5

   • Still none (p1 is at 10).
     Process SCHEDULE_PAYMENT p2 C A 20 8:
   • p2 scheduled from C to A for amount 20 at executeAt=8.

6. t=6: Before processing, execute all with executeAt ≤ 6

   • None (p2 is at 8).
     Process BALANCE A:
   • No scheduled payments executed yet, so A is still 100.
   • Append "100" to output.

7. t=7: Before processing, execute all with executeAt ≤ 7

   • None (p2 is at 8, p1 is at 10).
     Process CANCEL_PAYMENT p1:
   • p1 is now canceled and will never execute.

8. t=8: Before processing, execute all with executeAt ≤ 8

   • p2 has executeAt=8 and is pending:
     • At this moment, C has balance 50 and A has 100.
     • Execute p2: transfer 20 from C to A.
     • C balance = 30, A balance = 120.
     • C’s outgoing transfer total becomes 20.
   • p1 is canceled and not executed (even though executeAt=10 > 8). Process BALANCE A:
   • A balance is now 120; append "120".

9. t=9: Before processing, execute all with executeAt ≤ 9

   • No remaining pending payments with executeAt ≤ 9 (p1 is canceled). Process MERGE A C:
   • Merge C into A.
   • C balance = 30, so A balance becomes 120 + 30 = 150.
   • C is now closed and cannot be referenced in future commands.
   • Any pending scheduled payments involving C would be rewired to A, but there are none left.

10. t=10: Before processing, execute all with executeAt ≤ 10

    • p1 is canceled; nothing executes. Process BALANCE A:
    • A balance is 150; append "150".

11. t=11: Before processing, execute all with executeAt ≤ 11

    • No pending scheduled payments remain. Process TOP_SPENDERS 3:
    • Only one executed transfer: p2 (20 from C to A).
    • Outgoing transfer totals:
      • C: 20
      • A: 0 (no outgoing transfers)
      • B: 0
    • Only C has positive outgoing volume, even though C is now closed.
    • Top 3 spenders list is just [C].
    • Append "C".

Output:

text ["100", "120", "150", "C"]

---

Constraints

These constraints are a reasonable reconstruction for a medium-difficulty coding problem:

• Number of events:
  $$1 \leq N \leq 2 \times 10^5$$
• Timestamps:
  $$0 \leq t \leq 10^9$$, given in non-decreasing order.
• Account IDs and payment IDs:
  • Non-empty strings up to length 20.
  • Total number of distinct accounts ≤ $$N$$.
  • Total number of distinct payments ≤ $$N$$.
• Amounts and balances:
  • $$0 \leq \text{amount} \leq 10^9$$.
  • All balances fit in 64-bit signed integers (use 64-bit type).
• k in TOP_SPENDERS k:
  • $$1 \leq k \leq 10^5$$.
• Time and space complexity:
  • Expected to handle worst-case inputs within about $$O(N \log N)$$ time and $$O(N)$$ space.
  • A naive $$O(N^2)$$ solution will not scale.

---

Solution Hint

Use hash maps to track accounts, balances, and outgoing transfer totals; maintain scheduled payments in a min-heap keyed by executeAt (and paymentId as a tiebreaker) so you can efficiently execute all due payments before each event, and answer TOP_SPENDERS using a heap or partial sort over the accumulated outgoing transfer totals.