题目重点:从有符号交易累加扩展到逐笔透支拒绝和平台账户代垫,明确币种与 reserve 的未公开规则。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版按输入顺序处理,amount 为有符号变动:正数入账、负数支出;同一 account 的不同 currency 绝不直接相加。
- 透支版若 balance+amount<0 则整笔拒绝,余额不变,拒绝列表保持输入顺序。
- 平台代垫版先让用户余额从当前值降到 0,缺口从同币种平台账户扣除;平台余额不足时整笔拒绝且所有账户不变。max_reserve 的正式定义题目未充分说明,训练版取任一时刻平台累计代垫未偿还额的峰值,而不是臆造为官方答案。
解题路线
- 先把每行解析为 account、timestamp、currency、signed amount,保留原行供 rejected list 输出;显式验证列数、金额单位和 timestamp 是否要求排序。第一段用 (account,currency)→balance 聚合,只输出非零余额。
- 第二段逐笔试算 next=current+delta;若负数,记录拒绝原行且不改状态;否则提交。零余额可留在内部 map,但输出过滤。
- 第三段对发生缺口的支出先计算 shortage=−next,检查平台同币种余额足够后原子更新用户与平台余额,同时记一笔平台对用户的应收 reserve;若不足,不得只更新一侧。
- 币种、付款手续费、FX 兑换属于其他帖的独立追问,不能在此题默认跨币种弥补;平台自身的负支出与自借自还也要先规定。若用于真实账务,保留逐笔可重放记录并加幂等键,而非仅存余额快照。
手动走一遍
训练例 acct_p=1000 USD、acct_u 先收 400 USD,再支出 500 USD:第二段支出被拒,u 仍 400、p 仍 1000;第三段如果平台可代垫,u 变 0、p 变 900,reserve 增 100。题目此例把 100 称 max_reserve,但未展示还款和多笔场景,峰值定义必须当成训练约定。
规模与取舍
T 笔交易、A 个账户币种组合,单次 hash 查改期望 O(1),总 O(T+A) 时间与 O(A+T_rejected) 空间;若按时间戳排序则 O(T log T),但只有题面要求时间排序时才做。
易错点与追问
容易失分的边界
- 按金额正负理解反了,负数支出却写 balance−amount。
- 把不同币种余额直接相加。
- 被拒交易先改余额后 append rejected,导致状态污染。
- 平台代垫只减平台钱不记用户欠款,或平台不足时部分提交。
- 把题目明显的账号名笔误当测试真值。
继续深挖
- 用户后来入账应先还平台 reserve 吗?来源没有规则,如何提出两种合同?
- 同一时间戳多币种记录是否有全局顺序?
- 并发两笔提款都看到可用余额时怎样防双花?
