OAmaster
— / 4已做

01Banking System I (Top Spenders + Scheduled Payments + Merge)

Implement a simplified version of a banking system. All operations have a timestamp parameter (stringified ms, range 1 to 10⁹, strictly increasing).

Level 1 — Account Creation, Deposit, Transfer

  • create_account(timestamp, account_id) -> bool
  • deposit(timestamp, account_id, amount) -> int | None
  • transfer(timestamp, source_account_id, target_account_id, amount) -> int | None

Level 2 — Top Spenders

  • top_spenders(timestamp, n) -> list[str] — top n accounts by highest outgoing total (transfer source + pay). Format "account_id(total_outgoing)". Tiebreak alphabetically.

Level 3 — Scheduled Payments with 2% Cashback

  • pay(timestamp, account_id, amount) -> str | None — withdraw amount. Provides 2% cashback (rounded down) refunded 24 hours later (86_400_000 ms). Returns "payment{ordinal}". Cashback processes before any other transaction at its refund timestamp.
  • get_payment_status(timestamp, account_id, payment_id) -> str | None — "IN_PROGRESS" or "CASHBACK_RECEIVED".

Level 4 — Account Merging with Balance History

  • merge_accounts(timestamp, account_id_1, account_id_2) -> bool — merge account_id_2 into account_id_1. Pending cashbacks for account 2 still refund to account 1. Queries with old payment_id must still work via account 1.
  • get_balance(timestamp, account_id, time_at) -> int | None — historical balance after operations at time_at.

解法

四级状态机。账户字典维护 balance + outgoing + history。Cashback 用按 (refund_ts, payment_id) 排序的小顶堆，每次操作开头先 flush，确保同一时间戳的退款先于用户操作发生。合并用 merged_to 重定向表(并查集风格)让旧账户 id 和 payment id 仍能解析。get_balance 在账户历史列表上二分。多数操作均摊 O(log n)。设计题，只给 Python 实现。

import heapq, bisect
from collections import defaultdict
from typing import Optional, List

class Bank:
    DAY_MS = 86_400_000

    def __init__(self):
        self.accounts = {}
        self.payments = {}
        self.payment_counter = 0
        self.cashback_heap = []
        self.merged_to = {}

    def _resolve(self, aid):
        while aid in self.merged_to: aid = self.merged_to[aid]
        return aid

    def _flush_cashback(self, ts):
        while self.cashback_heap and self.cashback_heap[0][0] <= ts:
            refund_ts, pid = heapq.heappop(self.cashback_heap)
            pay = self.payments[pid]
            if pay["status"] == "CASHBACK_RECEIVED": continue
            aid = self._resolve(pay["account"])
            if aid not in self.accounts: continue
            refund = pay["amount"] // 50
            acc = self.accounts[aid]
            acc["balance"] += refund
            acc["history"].append((refund_ts, acc["balance"]))
            pay["status"] = "CASHBACK_RECEIVED"

    def create_account(self, ts, aid):
        self._flush_cashback(ts)
        if aid in self.accounts: return False
        self.accounts[aid] = {"balance": 0, "outgoing": 0, "history": [(ts, 0)]}
        return True

    def deposit(self, ts, aid, amount):
        self._flush_cashback(ts)
        aid = self._resolve(aid)
        if aid not in self.accounts: return None
        acc = self.accounts[aid]
        acc["balance"] += amount
        acc["history"].append((ts, acc["balance"]))
        return acc["balance"]

    def transfer(self, ts, src, dst, amount):
        self._flush_cashback(ts)
        src = self._resolve(src); dst = self._resolve(dst)
        if src == dst or src not in self.accounts or dst not in self.accounts: return None
        sa = self.accounts[src]
        if sa["balance"] < amount: return None
        sa["balance"] -= amount; sa["outgoing"] += amount
        self.accounts[dst]["balance"] += amount
        sa["history"].append((ts, sa["balance"]))
        self.accounts[dst]["history"].append((ts, self.accounts[dst]["balance"]))
        return sa["balance"]

    def top_spenders(self, ts, n):
        self._flush_cashback(ts)
        items = sorted(
            ((aid, acc["outgoing"]) for aid, acc in self.accounts.items()),
            key=lambda x: (-x[1], x[0])
        )
        return [f"{aid}({amt})" for aid, amt in items[:n]]

    def pay(self, ts, aid, amount):
        self._flush_cashback(ts)
        aid = self._resolve(aid)
        if aid not in self.accounts: return None
        acc = self.accounts[aid]
        if acc["balance"] < amount: return None
        acc["balance"] -= amount; acc["outgoing"] += amount
        acc["history"].append((ts, acc["balance"]))
        self.payment_counter += 1
        pid = f"payment{self.payment_counter}"
        cashback_ts = ts + self.DAY_MS
        self.payments[pid] = {"account": aid, "amount": amount, "cashback_ts": cashback_ts, "status": "IN_PROGRESS"}
        heapq.heappush(self.cashback_heap, (cashback_ts, pid))
        return pid

    def get_payment_status(self, ts, aid, pid):
        self._flush_cashback(ts)
        aid = self._resolve(aid)
        if aid not in self.accounts or pid not in self.payments: return None
        if self._resolve(self.payments[pid]["account"]) != aid: return None
        return self.payments[pid]["status"]

    def merge_accounts(self, ts, a1, a2):
        self._flush_cashback(ts)
        a1 = self._resolve(a1); a2 = self._resolve(a2)
        if a1 == a2 or a1 not in self.accounts or a2 not in self.accounts: return False
        acc1 = self.accounts[a1]; acc2 = self.accounts[a2]
        acc1["balance"] += acc2["balance"]
        acc1["outgoing"] += acc2["outgoing"]
        merged_hist = sorted(acc1["history"] + acc2["history"], key=lambda x: x[0])
        clean = []
        for tts, bal in merged_hist:
            if clean and clean[-1][0] == tts:
                clean[-1] = (tts, bal)
            else:
                clean.append((tts, bal))
        acc1["history"] = clean
        acc1["history"].append((ts, acc1["balance"]))
        self.merged_to[a2] = a1
        del self.accounts[a2]
        return True

    def get_balance(self, ts, aid, time_at):
        self._flush_cashback(ts)
        aid = self._resolve(aid)
        if aid not in self.accounts: return None
        hist = self.accounts[aid]["history"]
        keys = [h[0] for h in hist]
        idx = bisect.bisect_right(keys, time_at) - 1
        if idx < 0: return None
        return hist[idx][1]

02Bot Bank — Deposit/Withdraw with Cashback (Stateless solution)

You've been asked to program a bot for a popular bank. Every request has a timestamp in seconds (strictly increasing).

  • "deposit <timestamp> <holder_id> <amount>"
  • "withdraw <timestamp> <holder_id> <amount>" — withdraw + 2% cashback rounded down, refunded 24h (86400 sec) later. If the same timestamp triggers both a withdraw and a cashback, cashback happens first.

Invalid requests: invalid account number, or insufficient funds. Return final balances after last request, or [-request_id] (1-based) on first invalid.

解法

对请求单次扫描，待退款用按 refund_ts 排序的小顶堆。每条请求先 flush 所有 refund_ts ≤ ts 的退款再处理。首次非法立即返回 [-i](1 起)。复杂度 O((R + C) log C)，C 为退款数。

import heapq

def solution(balances, requests):
    n_acc = len(balances)
    bal = list(balances)
    cashback = []

    def flush(ts):
        while cashback and cashback[0][0] <= ts:
            rt, idx, amt = heapq.heappop(cashback)
            bal[idx] += amt

    for i, req in enumerate(requests, 1):
        parts = req.split()
        op, ts, hid, amt = parts[0], int(parts[1]), int(parts[2]), int(parts[3])
        flush(ts)
        if hid < 1 or hid > n_acc:
            return [-i]
        idx = hid - 1
        if op == "deposit":
            bal[idx] += amt
        elif op == "withdraw":
            if bal[idx] < amt: return [-i]
            bal[idx] -= amt
            cashback_amt = (amt * 2) // 100
            heapq.heappush(cashback, (ts + 86400, idx, cashback_amt))
        else:
            return [-i]
    return bal

03Banking System II (Optional Returns + Scheduled Payments + Merge)

Same 4-level structure as Problem 1, signatures use Optional<Integer> / Optional<String>.

Level 1

  • createAccount(ts, accountId) -> boolean
  • Optional<Integer> deposit(ts, accountId, amount)
  • Optional<Integer> transferMoney(ts, sourceAccountId, targetAccountId, amount)

Level 2 — Ranking

  • topSpenders(ts, n) — top n accounts by total outgoing. Format "accountId(total)".

Level 3 — Scheduled Payments

  • schedulePayment(ts, accountId, amount, delay) — schedule a payment that executes at ts + delay. Returns paymentN id.
  • cancelScheduledPayment(ts, paymentId) — only if still SCHEDULED.

Level 4 — Merge Accounts

  • boolean mergeAccounts(ts, accountId1, accountId2)
  • Optional<Integer> getBalance(ts, accountId, timeAt)

解法

与第 1 题同样的 4 级骨架，Level 3 把 cashback 换成显式的 schedulePayment / cancelScheduledPayment API；待执行付款用同样的小顶堆。状态机：SCHEDULED → EXECUTED / FAILED / CANCELLED。设计题，只给 Python 骨架。

import heapq

class Bank2:
    def __init__(self):
        self.accounts = {}
        self.scheduled = {}
        self.pay_counter = 0
        self.queue = []
        self.merged = {}

    def _resolve(self, aid):
        while aid in self.merged: aid = self.merged[aid]
        return aid

    def _flush_scheduled(self, ts):
        while self.queue and self.queue[0][0] <= ts:
            et, pid = heapq.heappop(self.queue)
            p = self.scheduled[pid]
            if p["status"] != "SCHEDULED": continue
            aid = self._resolve(p["account"])
            if aid not in self.accounts:
                p["status"] = "CANCELLED"; continue
            acc = self.accounts[aid]
            if acc["balance"] < p["amount"]:
                p["status"] = "FAILED"; continue
            acc["balance"] -= p["amount"]
            acc["outgoing"] += p["amount"]
            acc["history"].append((et, acc["balance"]))
            p["status"] = "EXECUTED"

    def schedulePayment(self, ts, aid, amt, delay):
        self._flush_scheduled(ts)
        aid = self._resolve(aid)
        if aid not in self.accounts: return None
        self.pay_counter += 1
        pid = f"payment{self.pay_counter}"
        exec_ts = ts + delay
        self.scheduled[pid] = {"account": aid, "amount": amt, "exec_ts": exec_ts, "status": "SCHEDULED"}
        heapq.heappush(self.queue, (exec_ts, pid))
        return pid

    def cancelScheduledPayment(self, ts, pid):
        self._flush_scheduled(ts)
        if pid not in self.scheduled: return False
        if self.scheduled[pid]["status"] != "SCHEDULED": return False
        self.scheduled[pid]["status"] = "CANCELLED"
        return True

04Accept or Decline Queries

Hi! I made a tiny modification in the input timestamps, it is supposed to be int[], but Java says it is too large as integer, so I have to change it to String[]. Things might be a bit more complicated, but I believe you can handle it :P Given a list of timestamped queries, you will need to accept or decline each of them, depending on the number of request from the same IP during a given window. The queries are represented by the two arrays timestamps and ipAddresses: timestamps, an array of integers representing the Unix timestamps of the requests. a. timestamps[i] represents the ith timestamp for the ith request, in milliseconds. b. All requests are guaranteed to be in chronological order, i.e., timestamps is sorted in non-decreasing order. c. It's guaranteed that no two requests from the same IP have the same timestamp. ipAddresses, an array of strings representing source IP addresses. d. ipAddresses[i] corresponds to the ith request's IP address. You're also given two integers limit and timeWindow: limit represents the maximum number of requests that can be accepted from the same IP address, within the time window. timeWindow represents the duration of the inclusive time window, in milliseconds. You must return an array of integers where the ith element of the array corresponds to the ith request. Each element of the array should equal to 1 if the ith request was accepted and 0 if it was rejected.

Example 1

Input:

timestamps = ["1600040547954", "1600040547957", "1600040547958"]
ipAddresses = ["127.127.420.312", "127.127.420.312", "127.127.420.312"]
limit = 1
timeWindow = 3

Output:

[1, 0, 1]

Explanation: Request at 0 has arrived at timestamp 1600040547954 from IP address 127.105.456.312, and since there are no accepted requests from 127.105.456.312, it's accepted. Thus 1. Request at 1 has arrived at timestamp 1600040547957 from IP address 127.105.456.312. There's already a request from the same IP address within the same time window so we reject. Thus 0. Request at 2 has arrived at timestamp 1600040547958 from IP address 127.105.456.312. There are no accepted requests from this IP address within this time window, it's accepted. Thus 1.

Example 2

Input:

timestamps = ["52245", "52245", "52246", "52247", "52248", "52249", "52253"]
ipAddresses = ["00.00.00.15", "00.00.00.42", "00.00.00.15", "00.00.00.15", "00.00.00.42", "00.00.00.15", "00.00.00.96"]
limit = 2
timeWindow = 3

Output:

[1, 1, 1, 0, 1, 1, 1]

Explanation: :)

Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁
Pro 会员

解锁全部 1 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部
  • 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
  • 📊个人 dashboard + 进度可视化 + 14 天活跃图
  • 📝题目笔记跨设备同步 + 个人复盘库
  • 🔓随时取消下次续费, Stripe Customer Portal 自助管理
$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月 的 23%

立即解锁 $98/年已是会员, 去登录

Affirm

Affirm OA 真题，三语题解(Python / Java / C++)。

Sofi

Sofi OA 真题，三语题解(Python / Java / C++)。