题目重点:IC5 题目给 place/pause/resume/cancel/complete、live 订单展示,以及 userId、cancelAll 和 n 流分区的连续追问。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- n>0,订单 ID 全局唯一;amount>0、timestamp 整数、type 为 buy/sell 的校验是训练版,题目只称 unique IDs 和属性。
- 同 timestamp 展示按插入序号稳定排序;题目只规定 timestamp 升序,未给并列规则。cancelAll 只取消 live/paused,已 completed/canceled 不计数。
- 分流训练版 stream=stableHash(userId)%n,持久化相同 hash 算法/版本;全局 ID→stream 路由索引或可导出的 userId,避免只凭 orderId 无法找到归属。
解题路线
- 订单表以 ID→Order 保存属性、state、userId、insertionSequence;把每个命令实现为状态转换表,非法转换返回空串,不修改对象。place 检查重复 ID;pause 仅 live→paused;resume 仅 paused→live;cancel 仅 live/paused→canceled;complete 仅 live→completed。
- displayLiveOrders 过滤 state=live,按 (timestamp,insertionSequence) 排序。若查询频繁,可维护 ordered index;任一状态变化需同步增删索引。
- 第二层维护 userId→order ID 集合,cancelAll 遍历该用户订单并复用 cancel 转换,只累计真正成功的订单数;重复调用第二次应返回 0。
- 第三层同用户订单进入同一 stream,写命令按 stream 内顺序处理;需要全局 display 时从各 stream 的有序 live 列表做 k-way merge。n 变化会改变 hash 归属,生产需稳定重分片/迁移版本,不能直接换 modulo 而丢路由。
- 测试每条合法/非法边、重复 place、同时间戳、跨用户 ID、cancelAll 幂等、n=1 与多 stream 路由;生产讨论写入原子性、命令重试和审计事件,但不能把这些说成题目必需。
手动走一遍
place A(t=7,user=u)→live;pause A→paused;complete A 此时非法,返回空串;resume A→live;complete A→completed;再 cancel A 非法。另有 B live、C paused 同属 u 时,cancelAll(u)=2,第二次调用返回 0。
规模与取舍
哈希表单命令平均 O(1),N 单 display 直接过滤排序 O(N log N)、O(N) 临时空间;有序索引状态更新 O(log N)、展示 O(L)。cancelAll(u) O(该用户历史订单数);S 流有序合并 L 个 live 订单 O(L log S)。
易错点与追问
容易失分的边界
- 把 pause 后订单也显示成 live。
- 允许 paused→completed,题目仅允许 complete live。
- cancelAll 把已完成订单计入成功数。
- 用语言内随机化 hash 做持久分流,重启后同用户流可能变化。
- 凭空加入 matching/settlement 流程,偏离命令状态题。
继续深挖
- n 从 4 扩成 8 时如何迁移用户流?
- 多流下全局 timestamp 稳定展示如何分页?
- 并发两个命令打到同订单时如何保证状态唯一?
- 若 cancelAll 遍历很慢,怎样批处理又保持结果计数?
