Design a Timestamped Cloud Credit Ledger with Rebates, Merges, and History

Problem Statement

Implement an in-memory credit ledger system, CloudCreditLedger, that manages user balances across discrete timestamps. All incoming operations arrive with non-decreasing timestamps.

The system must support top-ups, charges with delayed percentage-based rebates, merging accounts, historical point-in-time balance lookups, and spending rank queries.

Requirements

1. Rebate Processing:

   • Charges may schedule a delayed rebate: rebate_amount = floor(amount * rebate_pct / 100) to be credited at timestamp + rebate_delay.
   • Before executing any operation at time T, all scheduled rebates with scheduled_time <= T must be applied.
   • If multiple rebates mature at the same timestamp, process them in the order their corresponding charges were created.
   • Rebates credit the canonical target account (resolving merges) and do not reduce the account's gross spending record.

2. Account Merges:

   • Merging source_id into target_id at time T transfers source_id's remaining balance at T into target_id.
   • Subsequent operations referencing source_id are automatically redirected to target_id.
   • Account merges are transitive (if A merges into B, and B merges into C, A resolves to C).
   • Historical balance queries for source_id at query_time < T must return the exact balance source_id possessed at query_time before the merge.

3. Spending Leaderboard:

   • Accounts are ranked by total gross credits spent via successful charges.
   • When accounts merge, their historical gross spending totals are merged into the target account.
   • Ties in total spending are broken alphabetically by the canonical account ID.

Class Interface

class CloudCreditLedger:
    def __init__(self):
        pass

    def top_up(self, timestamp: int, account_id: str, amount: int) -> bool:
        """Adds amount to the account's balance. Returns True if amount > 0, else False."""
        pass

    def charge(self, timestamp: int, account_id: str, amount: int, rebate_delay: int, rebate_pct: int) -> bool:
        """Attempts to charge amount. If canonical balance >= amount, deducts amount and
        schedules a rebate for floor(amount * rebate_pct / 100) at timestamp + rebate_delay.
        Returns True on success, False if insufficient balance or amount  bool:
        """Merges source_id into target_id. Returns False if source_id == target_id,
        or if either account does not exist. Otherwise transfers source balance to target."""
        pass

    def get_balance(self, timestamp: int, account_id: str) -> int:
        """Returns the current balance of account_id's canonical account after processing
        rebates up to timestamp. Returns -1 if account does not exist."""
        pass

    def get_historical_balance(self, timestamp: int, account_id: str, query_time: int) -> int:
        """Returns the balance account_id specifically held at query_time (query_time <= timestamp).
        Does NOT resolve to merge target if query_time is prior to account_id being merged.
        Returns -1 if account did not exist at query_time."""
        pass

    def get_top_spenders(self, timestamp: int, k: int) -> list[str]:
        """Returns up to k canonical account IDs with the highest gross spending.
        Ties broken alphabetically."""
        pass

Constraints

• Timestamps in method calls are strictly non-decreasing: t_prev <= t_curr.
• 0 <= query_time <= timestamp <= 10^9
• 1 <= amount <= 10^6
• 0 <= rebate_delay <= 10^6, 0 <= rebate_pct <= 100
• Up to 100,000 total method invocations.

Examples

ledger = CloudCreditLedger()
ledger.top_up(10, "acc_1", 100)            # True (acc_1 balance: 100)
ledger.charge(12, "acc_1", 60, 5, 50)       # True (acc_1 balance: 40; rebate of 30 due at t=17)
ledger.get_balance(15, "acc_1")             # 40 (rebate not yet due)
ledger.get_balance(17, "acc_1")             # 70 (rebate of 30 applied)
ledger.get_historical_balance(18, "acc_1", 14)  # 40

ledger.top_up(20, "acc_2", 50)            # True
ledger.merge_accounts(25, "acc_1", "acc_2") # True (acc_1 merged into acc_2; acc_2 balance: 70 + 50 = 120)
ledger.get_balance(26, "acc_1")             # 120 (resolves to acc_2)
ledger.get_historical_balance(26, "acc_1", 20)  # 70 (pre-merge balance of acc_1)
ledger.get_top_spenders(26, 2)             # ["acc_2"] (acc_2 absorbed acc_1's 60 spent)