#10 Banking System (Online Assessment) — Solution

✦ AI-Generated Solution · Coding (OA) · Comprehensive Full level-by-level reference implementation, including the hard parts: lazy 24h cashback processing, account merging with redirected refunds, and historical balance queries. Verified with an end-to-end assertion suite covering all four levels.

How to approach this OA

The defining difficulty is time. Timestamps arrive strictly increasing, but cashback lands in the future (timestamp + 86_400_000). You cannot eagerly schedule a callback, so use the standard trick: keep a list of pending refunds and, at the start of every operation, lazily apply all pending refunds whose execution time is <= current timestamp. Because timestamps are monotonic, this is correct and amortized-cheap.

State to carry across all levels:

• accounts: id -> balance, outgoing: id -> total outgoing (transfers out + payments).
• history: id -> [(timestamp, balance), ...] to answer Level-4 get_balance(time_at) via binary search. A merged/removed account gets a terminal (merge_ts, None) marker so queries at/after the merge return None but earlier history stays queryable.
• pending: [(exec_time, account, cashback, payment_id)] and a payments registry for status.

Reference Implementation (Python)

import bisect

class BankingSystem:
    def __init__(self):
        self.accounts = {}      # id -> balance
        self.outgoing = {}      # id -> total outgoing
        self.history  = {}      # id -> [(ts, balance)]  (balance None = removed)
        self.payments = {}      # payment_id -> {account, exec_time, status_time}
        self.pending  = []      # [(exec_time, account, cashback, payment_id)]
        self.pay_counter = 0
    CASHBACK_DELAY = 86_400_000

    # apply every refund whose time has arrived (monotonic timestamps -> safe)
    def _process_cashback(self, ts):
        self.pending.sort()
        keep = []
        for exec_time, acc, amount, pid in self.pending:
            if exec_time <= ts:
                if acc in self.accounts:                # skip if account removed
                    self.accounts[acc] += amount
                    self._record(acc, exec_time)
                self.payments[pid]["status_time"] = exec_time
            else:
                keep.append((exec_time, acc, amount, pid))
        self.pending = keep

    def _record(self, acc, ts):
        h = self.history.setdefault(acc, [])
        if h and h[-1][0] == ts:
            h[-1] = (ts, self.accounts[acc])
        else:
            h.append((ts, self.accounts[acc]))

    # ---------- Level 1 ----------
    def create_account(self, ts, account_id):
        self._process_cashback(ts)
        if account_id in self.accounts:
            return False
        self.accounts[account_id] = 0
        self.outgoing[account_id] = 0
        self.history[account_id] = [(ts, 0)]
        return True

    def deposit(self, ts, account_id, amount):
        self._process_cashback(ts)
        if account_id not in self.accounts:
            return None
        self.accounts[account_id] += amount
        self._record(account_id, ts)
        return self.accounts[account_id]

    def transfer(self, ts, source, target, amount):
        self._process_cashback(ts)
        if source not in self.accounts or target not in self.accounts:
            return None
        if source == target or self.accounts[source] < amount:
            return None
        self.accounts[source] -= amount
        self.accounts[target] += amount
        self.outgoing[source] += amount
        self._record(source, ts); self._record(target, ts)
        return self.accounts[source]

    # ---------- Level 2 ----------
    def top_spenders(self, ts, n):
        self._process_cashback(ts)
        ranked = sorted(self.outgoing.items(), key=lambda x: (-x[1], x[0]))
        return [f"{acc}({amt})" for acc, amt in ranked[:n]]

    # ---------- Level 3 ----------
    def pay(self, ts, account_id, amount):
        self._process_cashback(ts)
        if account_id not in self.accounts or self.accounts[account_id] < amount:
            return None
        self.accounts[account_id] -= amount
        self.outgoing[account_id] += amount
        self._record(account_id, ts)
        self.pay_counter += 1
        pid = f"payment{self.pay_counter}"
        cashback = (amount * 2) // 100                   # 2%, floored
        exec_time = ts + self.CASHBACK_DELAY
        self.payments[pid] = {"account": account_id, "exec_time": exec_time, "status_time": None}
        self.pending.append((exec_time, account_id, cashback, pid))
        return pid

    def get_payment_status(self, ts, account_id, payment):
        self._process_cashback(ts)
        if account_id not in self.accounts:
            return None
        p = self.payments.get(payment)
        if p is None or p["account"] != account_id:
            return None
        if p["status_time"] is not None and p["status_time"] <= ts:
            return "CASHBACK_RECEIVED"
        return "IN_PROGRESS"

    # ---------- Level 4 ----------
    def merge_accounts(self, ts, acc1, acc2):
        self._process_cashback(ts)
        if acc1 == acc2 or acc1 not in self.accounts or acc2 not in self.accounts:
            return False
        self.accounts[acc1] += self.accounts[acc2]
        self.outgoing[acc1] += self.outgoing[acc2]
        # pending cashbacks for acc2 now pay out to acc1
        self.pending = [(t, acc1 if a == acc2 else a, amt, pid)
                        for (t, a, amt, pid) in self.pending]
        for p in self.payments.values():
            if p["account"] == acc2:
                p["account"] = acc1
        self._record(acc1, ts)
        self.history[acc2].append((ts, None))            # terminal marker
        del self.accounts[acc2]; del self.outgoing[acc2]
        return True

    def get_balance(self, ts, account_id, time_at):
        self._process_cashback(ts)
        h = self.history.get(account_id)
        if not h:
            return None
        idx = bisect.bisect_right([t for t, _ in h], time_at) - 1
        if idx < 0:
            return None
        _, bal = h[idx]
        return bal                                       # None if removed at/before time_at

The traps that fail hidden tests

1. Process cashbacks at the start of every op, not just inside get_payment_status. A top_spenders or get_balance call at a later timestamp must already reflect refunds that became due.
2. Cashback is 2% floored (amount * 2 // 100), and it is excluded from outgoing — only money leaving the account (transfers out + payments) counts toward top_spenders.
3. Refund to a removed account is dropped, unless the account was merged — in which case the pending refund is redirected to the surviving account at merge time.
4. get_balance is historical: binary-search the balance snapshots for the latest record <= time_at. After a merge, the absorbed account returns its pre-merge history for time_at < merge_ts and None afterward (until/unless recreated, which starts fresh at 0).
5. top_spenders tie-break is alphabetical ascending on account_id; format each entry as "id(total_outgoing)".

Complexity

• create/deposit/transfer/pay/get_payment_status: O(P log P) worst case from the pending-refund sweep (P = pending refunds), amortized near O(1) since each refund is processed once.
• top_spenders: O(A log A) in number of accounts.
• get_balance: O(H) to build the key list (or O(log H) if you keep a parallel sorted key array).

Verification

An end-to-end assertion suite exercises account creation/duplication, deposits to missing accounts, self-transfer and insufficient-funds guards, top_spenders ranking and ties, a pay with a 24h-delayed 2% cashback, status transition IN_PROGRESS -> CASHBACK_RECEIVED, historical get_balance before vs. after the cashback, an account merge with redirected payment status, and recreation of a merged id. All assertions pass:

Banking: ALL ASSERTIONS PASS