IC5 / SWE · Onsite Tech Execution Coding

Coinbase CryptoTradingSystem:订单状态、多用户取消与分流

IC5 题目给 place/pause/resume/cancel/complete、live 订单展示,以及 userId、cancelAll 和 n 流分区的连续追问。

题目重点: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 无法找到归属。

解题路线

  1. 订单表以 ID→Order 保存属性、state、userId、insertionSequence;把每个命令实现为状态转换表,非法转换返回空串,不修改对象。place 检查重复 ID;pause 仅 live→paused;resume 仅 paused→live;cancel 仅 live/paused→canceled;complete 仅 live→completed。
  2. displayLiveOrders 过滤 state=live,按 (timestamp,insertionSequence) 排序。若查询频繁,可维护 ordered index;任一状态变化需同步增删索引。
  3. 第二层维护 userId→order ID 集合,cancelAll 遍历该用户订单并复用 cancel 转换,只累计真正成功的订单数;重复调用第二次应返回 0。
  4. 第三层同用户订单进入同一 stream,写命令按 stream 内顺序处理;需要全局 display 时从各 stream 的有序 live 列表做 k-way merge。n 变化会改变 hash 归属,生产需稳定重分片/迁移版本,不能直接换 modulo 而丢路由。
  5. 测试每条合法/非法边、重复 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 遍历很慢,怎样批处理又保持结果计数?
✓已复制微信号!