题目重点:把转账冻结、accept、cashback 变体、merge account 和历史查询拆为状态机,重点解释合并后重建相同 account id 的身份问题。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练设计以整数最小货币单位计数,所有操作带单调时间戳;禁止负金额和给自己转账。题目没有写金额类型与并列排序规则,正式作答需确认。
- 一个文本 account_id 可多次创建,每次生命周期分配不同 incarnation_id;历史查询同时指定 ID 和查询时间,定位那时有效的生命周期。
- 转账创建时从可用余额扣除并进入 pending liability;accept 才给接收账户加余额;取消、过期、合并时待处理转账的去向由具体 OA 变体决定,本文只演示一套明确的训练规则。
解题路线
- 将账户主键拆为 `(external_id,incarnation)`,活跃映射仅指向最新仍开放的一代。每个生命周期保存开立、关闭/合并时间与余额事件;历史不能直接读当前活跃映射。
- 转账状态机为 `PENDING→ACCEPTED/EXPIRED/CANCELLED`,转账记录保存发送者和目标生命周期、金额、创建时间与稳定 transfer id。创建转账的余额守恒式是 `available_sender -= amount; pending_liability += amount`;accept 时 `pending_liability -= amount; available_receiver += amount`。重复 accept 应返回原结果,不再入账。
- merge(primary,secondary) 在单次原子操作里移动 secondary 的可用余额、结清或迁移其未决转账,并标记 secondary 生命周期关闭。训练版把指向已合并 secondary 的未决入账定向到 primary;secondary 的未决出账仍由其原 transfer id 负责,不在 merge 时再扣钱。
- 为历史余额使用按 incarnation 分开的时间有序事件或快照,查询先找 t 所属生命周期,再二分到最后一个事件。若 secondary 后来用相同文本 id 重建,新 incarnation 从零开始,不能继承旧余额、旧未决转账或旧 cashback。
- spending 排名与 cashback 是另一版的同系统 level:实际支出、冻结金额、退款与 cashback 发生时刻必须分开累计;题目未明确比例、延迟或排序 tie-break,不把任何数值写成原题要求。
手动走一遍
训练例:t=1 建 A/B,A=100、B=20;t=2 A 向 B 发起 30,A 可用 70、pending 30、B 20;t=3 合并 B 到 A,A 可用 90、旧 B 生命周期关闭;t=4 接受原转账,30 进入合并目标 A,A 可用 120、pending 0。t=5 重建文本 ID B,新 B 余额 0;查 t=2 的 B 仍为旧生命周期余额 20,而不是新 B 的 0。此例中合并/accept 顺序是本文训练约定。
规模与取舍
哈希状态下创建、入金、转账、accept、merge 的基础查找平均 O(1),但 merge 需要迁移 secondary 相关未决转账时成本 O(P_secondary);历史事件数 H 时,若按账户维护有序事件,可 O(log H) 定位时间加 O(1) 读快照,若每次回放全部事件则 O(H)。总状态 O(账户生命周期数+转账数+历史事件数)。
易错点与追问
容易失分的边界
- 把 account_id 当永久唯一身份,同名重建后历史查询串到新账户。
- 未接受转账既不扣可用余额又不预留,发送者可重复花同一笔钱。
- merge 只加两边余额,漏处理 pending 转账,接受时可能双计或丢钱。
- cashback 与 spending 在支付创建、结算或退款时何时变动未先定合同。
- 把本文合并后的转账定向规则当作已公开原题;题目只指出这是难点。
继续深挖
- 若 pending 转账超时,退款应回旧发送者生命周期还是合并后的 survivor?
- 如何处理同一时间戳的创建、合并、accept 和历史查询顺序?
- 如果要支持撤销合并或审计账本,为什么只存当前余额不够?
