Extend a Banking Interface with Scheduled Payments and Account Merges

Problem Statement

You are tasked with extending an in-memory banking ledger to support scheduled payments and account merges. All monetary values are represented as non-negative integers (cents).

Implement the BankingSystem class with the following methods:

class BankingSystem:
    def __init__(self):
        pass

    def create_account(self, account_id: str, initial_balance: int) -> bool:
        pass

    def schedule_payment(self, payment_id: str, timestamp: int, from_account: str, to_account: str, amount: int) -> bool:
        pass

    def cancel_payment(self, payment_id: str) -> bool:
        pass

    def merge_accounts(self, source_account: str, target_account: str) -> bool:
        pass

    def advance_time(self, current_time: int) -> list[dict]:
        pass

    def get_balance(self, account_id: str) -> int:
        pass

Requirements and Rules

1. Account Creation: create_account creates an account with initial_balance >= 0. Returns False if account_id already exists or was previously merged, otherwise True.
2. Account Merging:
   • merge_accounts(source, target) consolidates source into target.
   • source is permanently retired. Its entire current balance is added to target. If source was already retired, or target is retired/does not exist, return False. If source == target, return False.
   • Any existing scheduled payments involving source (as sender or receiver) that execute in the future must automatically be re-routed to use target.
   • Any chain of merges must be resolved (e.g., if A merges into B, and B later merges into C, transactions originally targeting A now route to C).
   • Returns True on success.
3. Scheduled Payments & Idempotency:
   • schedule_payment schedules a payment to execute at timestamp.
   • If payment_id was already registered (regardless of whether it executed, failed, or was cancelled), return False.
   • If from_account or to_account does not exist (or resolves to the exact same account after merge resolution), return False.
   • amount must be greater than 0.
4. Cancellation: cancel_payment cancels a payment if it exists and has not yet executed. Returns True if cancelled, False if the payment does not exist or has already executed/failed/cancelled.
5. Execution (advance_time):
   • Processes all pending scheduled payments with payment.timestamp <= current_time.
   • Deterministic Order: Payments with smaller timestamps execute first. For payments with identical timestamps, order alphabetically (ascending) by payment_id.
   • Execution Logic: For each payment, resolve from_account and to_account to their active target accounts. If from_account balance is < amount, the payment fails (status "FAILED") and no money moves. Otherwise, deduct amount from from_account and add amount to to_account (status "SUCCESS").
   • Returns a list of dicts in execution order: {"payment_id": str, "status": "SUCCESS" | "FAILED", "timestamp": int}.
6. Balance Query: get_balance returns the current balance of the resolved active account. If the account does not exist and was never created, return -1.

Example

bank = BankingSystem()
bank.create_account("acc1", 100)
bank.create_account("acc2", 50)
bank.create_account("acc3", 0)

# Schedule payments
bank.schedule_payment("p2", 10, "acc1", "acc2", 60)  # timestamp 10
bank.schedule_payment("p1", 10, "acc1", "acc3", 50)  # timestamp 10

# At timestamp 10, p1 executes before p2 due to lexicographical order of IDs
# p1 succeeds (acc1: 100 -> 50, acc3: 0 -> 50)
# p2 then attempts to transfer 60 from acc1, but acc1 only has 50 -> Fails
results = bank.advance_time(10)
# results == [
#     {"payment_id": "p1", "status": "SUCCESS", "timestamp": 10},
#     {"payment_id": "p2", "status": "FAILED", "timestamp": 10}
# ]

# Merge acc3 into acc2
bank.merge_accounts("acc3", "acc2")
# acc3 balance (50) is merged into acc2 (50 + 50 = 100)
assert bank.get_balance("acc2") == 100
assert bank.get_balance("acc3") == 100  # acc3 resolves to acc2