Bank System

Problem Overview

Design and implement a banking system that supports account creation, fund transfers, spending analytics, scheduled payments, and account merging. This is a multi-level problem where each level builds upon the previous one.

All operations receive a timestamp parameter (a positive integer in milliseconds). Timestamps are guaranteed to be non-decreasing across calls (multiple operations can share the same timestamp). Scheduled payments introduce additional execution at their due times.

You'll build this incrementally across four levels.

Level 1: Basic Banking Operations

Problem Statement

Implement a BankSystem class that supports creating accounts, depositing funds, and transferring money between accounts.

class BankSystem:
    def __init__(self):
        """Initialize the banking system."""
        pass

    def create_account(self, timestamp: int, account_id: str) -> bool:
        """
        Create a new bank account with a zero balance.

        Args:
            timestamp: The current time in milliseconds.
            account_id: Unique identifier for the account.

        Returns:
            True if the account was successfully created,
            False if an account with the same ID already exists.
        """
        pass

    def deposit(self, timestamp: int, account_id: str, amount: int) -> bool:
        """
        Deposit funds into an existing account.

        Args:
            timestamp: The current time in milliseconds.
            account_id: The account to deposit into.
            amount: The amount to deposit (positive integer).

        Returns:
            True if the deposit was successful,
            False if the account does not exist.
        """
        pass

    def transfer(self, timestamp: int, source_id: str, target_id: str, amount: int) -> bool:
        """
        Transfer funds from one account to another.

        Args:
            timestamp: The current time in milliseconds.
            source_id: The account to transfer from.
            target_id: The account to transfer to.
            amount: The amount to transfer (positive integer).

        Returns:
            True if the transfer was successful,
            False if either account does not exist, source and target
            are the same, or source has insufficient funds.
        """
        pass

Example Usage

bank = BankSystem()

bank.create_account(1, "acc1")    # True
bank.create_account(2, "acc2")    # True
bank.create_account(3, "acc1")    # False (duplicate)

bank.deposit(4, "acc1", 1000)     # True
bank.deposit(5, "acc3", 500)      # False (account doesn't exist)

bank.transfer(6, "acc1", "acc2", 300)  # True (acc1: 700, acc2: 300)
bank.transfer(7, "acc1", "acc2", 800)  # False (insufficient funds)
bank.transfer(8, "acc1", "acc1", 100)  # False (same account)

---

Level 2: Top Spenders

Problem Statement

Extend the system to track outgoing transfer amounts and return the top spenders.

def top_spenders(self, timestamp: int, n: int) -> list:
    """
    Return the top N accounts ranked by total outgoing transfer amount.

    Args:
        timestamp: The current time in milliseconds.
        n: The number of top spenders to return.

    Returns:
        A list of strings in the format "account_id(total_outgoing)",
        sorted by total outgoing amount in descending order. If two
        accounts have the same total outgoing amount, sort them
        alphabetically by account_id. If there are fewer than n
        accounts with outgoing transfers, return all of them.

    Notes:
        - Only successful transfers count toward outgoing totals.
        - Deposits do not count as outgoing.
    """
    pass

Example Usage

bank = BankSystem()

bank.create_account(1, "acc1")
bank.create_account(2, "acc2")
bank.create_account(3, "acc3")

bank.deposit(4, "acc1", 2000)
bank.deposit(5, "acc2", 1000)
bank.deposit(6, "acc3", 500)

bank.transfer(7, "acc1", "acc2", 500)
bank.transfer(8, "acc2", "acc3", 300)
bank.transfer(9, "acc1", "acc3", 200)

bank.top_spenders(10, 2)
# ["acc1(700)", "acc2(300)"]
# acc1 transferred out 500 + 200 = 700
# acc2 transferred out 300

bank.top_spenders(11, 5)
# ["acc1(700)", "acc2(300)"]
# acc3 has no outgoing transfers, so only 2 results

---

Level 3: Scheduled Payments

Problem Statement

The system should allow scheduling payments and cancelling them. A scheduled payment is an outgoing payment that will be deducted from the account at a future time (timestamp + delay).

def schedule_payment(self, timestamp: int, account_id: str, amount: int, delay: int) -> str:
    """
    Schedule a payment to be executed at timestamp + delay.

    Args:
        timestamp: The current time in milliseconds.
        account_id: The source account for the payment.
        amount: The amount to deduct from the account.
        delay: The delay in milliseconds before the payment is executed.

    Returns:
        A unique payment ID in the format "payment[N]" where N is the
        ordinal number of the scheduled payment across all accounts
        (e.g., "payment1", "payment2", etc.).
        Returns "" (empty string) if the account does not exist.

    Notes:
        - The payment is skipped if the account has insufficient funds
          when the payment is due.
        - Successful payments should count as outgoing transactions
          and be reflected in top_spenders.
        - Scheduled payments should be processed BEFORE any other
          operations at the given timestamp.
        - If multiple scheduled payments are due at the same time,
          they should be processed in order of creation (e.g.,
          "payment1" before "payment2").
    """
    pass

def cancel_payment(self, timestamp: int, account_id: str, payment_id: str) -> bool:
    """
    Cancel a scheduled payment.

    Args:
        timestamp: The current time in milliseconds.
        account_id: The account that scheduled the payment.
        payment_id: The ID of the payment to cancel.

    Returns:
        True if the payment was successfully cancelled,
        False if the payment_id does not exist, was already
        cancelled, was already executed, or if account_id
        does not match the source account of the scheduled payment.

    Notes:
        - Scheduled payments due at the current timestamp must be
          processed BEFORE any cancel_payment operations at the
          same timestamp.
    """
    pass

Processing Order

At any given timestamp, operations are processed in this order:

1. Execute all due scheduled payments (in order of creation)
2. Process the current operation (deposit, transfer, cancel_payment, etc.)

This means a cancel_payment call cannot cancel a payment that is due at the same timestamp — the payment will have already been executed.

Example Usage

bank = BankSystem()

bank.create_account(1, "acc1")
bank.create_account(2, "acc2")
bank.deposit(3, "acc1", 1000)

# Schedule a payment from acc1 for 500, due at timestamp 103 (3 + 100)
pid1 = bank.schedule_payment(3, "acc1", 500, 100)
# Returns "payment1"

# Schedule another payment from acc1 for 300, due at timestamp 153 (3 + 150)
pid2 = bank.schedule_payment(3, "acc1", 300, 150)
# Returns "payment2"

# Cancel the second payment
bank.cancel_payment(50, "acc1", pid2)
# Returns True

# At timestamp 103, payment1 executes automatically before any operation
# acc1 balance: 1000 - 500 = 500
bank.deposit(103, "acc1", 200)
# acc1 balance: 500 + 200 = 700

# payment2 was cancelled, so nothing happens at timestamp 153
bank.deposit(153, "acc1", 100)
# acc1 balance: 700 + 100 = 800

bank.top_spenders(200, 5)
# ["acc1(500)"] — the scheduled payment counted as outgoing

---

Level 4: Account Merging and Historical Balance

Problem Statement

Add the ability to merge two accounts and query the balance of an account at a specific point in time.

def merge_accounts(self, timestamp: int, account_id1: str, account_id2: str) -> bool:
    """
    Merge account_id2 into account_id1.

    Args:
        timestamp: The current time in milliseconds.
        account_id1: The target account (survives the merge).
        account_id2: The source account (removed after merge).

    Returns:
        True if the merge was successful, False if either account
        does not exist or they are the same account.

    Notes:
        - account_id2's balance is added to account_id1.
        - account_id2 is removed from the system after merging.
        - Any scheduled payments from account_id2 should be
          transferred to account_id1.
        - account_id2's outgoing totals should be merged into
          account_id1's outgoing totals for top_spenders.
    """
    pass

def get_balance(self, timestamp: int, account_id: str, time_at: int) -> int:
    """
    Get the balance of an account at a specific historical timestamp.

    Args:
        timestamp: The current time in milliseconds.
        account_id: The account to query.
        time_at: The historical timestamp to query the balance at.

    Returns:
        The balance of the account at time_at, or -1 if the account
        did not exist at time_at.

    Notes:
        - If the account was merged into another account before
          time_at, return -1 (the old account no longer existed).
        - If querying a timestamp before the account was created,
          return -1.
        - If the account existed at time_at but has since been
          merged away, still return its balance at that time.
          Historical queries should work even for accounts that
          no longer exist.
    """
    pass

Corner Cases

1. Merged account queries: After merging acc2 into acc1, querying get_balance(ts, "acc2", time_before_merge) should still return acc2's balance at that time — even though acc2 no longer exists.
2. Post-merge queries: Querying get_balance(ts, "acc2", time_after_merge) should return -1 since acc2 didn't exist after the merge.
3. Scheduled payment transfer: Scheduled payments from the merged account should be reassigned to the surviving account.

Example Usage

bank = BankSystem()

bank.create_account(1, "acc1")
bank.create_account(2, "acc2")

bank.deposit(3, "acc1", 1000)
bank.deposit(4, "acc2", 500)

bank.transfer(5, "acc1", "acc2", 200)
# acc1: 800, acc2: 700

bank.merge_accounts(6, "acc1", "acc2")
# acc1: 800 + 700 = 1500, acc2: removed

# Historical query for acc2 before merge — should still work
bank.get_balance(7, "acc2", 5)
# 700 (acc2's balance at timestamp 5)

# Historical query for acc2 after merge — account didn't exist
bank.get_balance(8, "acc2", 6)
# -1

# Current balance of acc1
bank.get_balance(9, "acc1", 9)
# 1500

---

Follow-Up Discussion Topics