Two Sigma 作为顶级 Quant Fund（量化基金），其面试难度向来是业界标杆。最近流出的 OA（Online Assessment）给了 120分钟 完成 2道算法题。
很多同学一看："两小时做两道？这也太宽裕了吧！"
千万别大意。 Two Sigma 的题目往往题目描述长、业务逻辑复杂、Corner Case 极多。时间给得长，是因为题目真的需要你花时间去"抠细节"。
我们 oavoservice 团队第一时间拿到了真题，带大家拆解一下这两道题的"暗坑"。
🔍 真题一：IPO Share Allocation (IPO 股份分配)
题目核心： 模拟股票 IPO 的竞价和分配过程。
竞价规则： 用户提交 (id, shares, price, timestamp)。
分配逻辑： 优先给出价最高的人。
关键难点： 如果最高价有多人，且剩余股票不够分怎么办？
规则是 Round Robin（轮询）：在同价位组内，按时间戳排序，每人先分 1 股，循环进行，直到每个人分够了或者股票分完了。
输出： 返回所有一股都没分到的倒霉蛋 ID，按升序排列。
oavoservice 独家解析：
这道题披着"业务逻辑"的外衣，实则考察 复杂模拟 + 多级排序。
坑点 1 (Round Robin)： 很多同学直接按时间排序后一把梭哈分配，这是错的！题目要求是"一人一股轮着发"。
这意味着如果剩余 3 股，有 2 个人，A想要 10 股，B想要 10 股。
- 第一轮：A拿1，B拿1（剩1股）
- 第二轮：A拿1（分完）
结果是 A拿2股，B拿1股。而不是 A直接拿2股，B拿1股（虽然结果一样，但如果 A 只想要 1 股，逻辑就完全不同了）。
坑点 2 (数据结构)： 需要使用 PriorityQueue 或者自定义 Comparator 对 Bids 进行多级排序（Price DESC -> Timestamp ASC）。
解题思路：
- 将 Bids 按 Price 分组
- 从高价组开始处理，如果该组总需求 <= 剩余股票，直接满足
- 如果该组总需求 > 剩余股票，进入 while 循环模拟 Round Robin 分配
- 记录所有获得 >0 股的用户，最后与总用户集合做差集
🔍 真题二：Sewer Drainage System (下水道排水系统)
题目核心： 给定一个树形结构的排水系统，parent[i] 表示水从 i 流向 parent[i]。input[i] 是该节点的进水量。
任务： 切断一条边，将树分成两部分，使得两部分的总流量之差绝对值最小。
oavoservice 独家解析：
这是一道经典的 Tree DP / DFS 题目。
模型转换： 虽然题目说水流向 root，但切断一条边本质上就是把某个节点 u 及其所有子节点（Subtree）分离出去。
数学推导：
- 设整棵树的总流量为 TotalSum
- 设切断节点 i 与其父节点的边，得到的子树流量为 SubtreeSum[i]
- 那么另一部分的流量就是 TotalSum - SubtreeSum[i]
我们需要最小化：| (TotalSum - SubtreeSum[i]) - SubtreeSum[i] |
即最小化：| TotalSum - 2 * SubtreeSum[i] |
解题思路：
- 建图： 根据 parent 数组构建 Adjacency List（邻接表），注意题目给的是"子指向父"，我们需要转成"父指向子"以便做 DFS
- 计算总流量： 遍历 input 数组求和得到 TotalSum
- DFS 后序遍历： 自底向上计算每个节点的 SubtreeSum（包含自身的 input + 所有子节点的 SubtreeSum）
- 在计算过程中，代入公式
| TotalSum - 2 * SubtreeSum |更新全局最小值
复杂度： 时间 O(N)，空间 O(N)
💡 为什么 120 分钟还是有人挂？
这两道题虽然算法模型不偏门，但在高压环境下：
- 第一题的 Round Robin 模拟 极易写出 Infinite Loop 或者索引越界
- 第二题的 建树过程 容易出错（Parent 数组的处理）
- Two Sigma 的 Test Cases 覆盖极广，稍有疏忽就是 Runtime Error
如果你正在准备 Two Sigma, TikTok, Google, Amazon 等大厂的算法与系统设计面试
或者面对 OA 感到心里没底：欢迎联系我们！
我们要做的不仅是"做对"，更是"满分通过"。
✅ OA 代写 / 笔试保过： 覆盖 Two Sigma, Citadel, JS 等顶级 Quant 以及各路 Tech 大厂
✅ 算法面试辅助： 实时解决 Hard 难度的 Coding 题
✅ 稳定、安全、高效： 长期的实战经验，助您早日上岸
👉 立即添加微信：Coding0201
获取最新大厂 OA 真题库 & 免费咨询服务！