1. Two Sigma OA面试概述
作为量化金融领域的顶级公司，Two Sigma的在线评估(OA)环节向来以高难度著称。我最近完整经历了他们的OA流程，三题全部一次通过，这里将详细复盘整个经历。不同于网上零散的题目分享，本文会重点拆解每道题的解题思路、时间分配策略以及那些容易踩坑的细节。
Two Sigma的OA系统采用自主研发的测评平台，题目类型主要涵盖算法优化和统计建模两大方向。根据我和多位面试者的交流，题目难度普遍达到LeetCode Hard级别，但更侧重考察对基础算法的创造性应用能力。整个OA时长通常为90分钟，需要在有限时间内完成3-4道编程题。
关键提示：Two Sigma的OA题目往往有多个隐藏的边界条件，表面看起来是经典算法题，实则都经过精心改造，需要特别注意题目描述中的每个限定词。
2. 题目一：带约束的最短路径问题
2.1 题目描述还原
给定一个带权有向图，要求找出从起点到终点的最短路径，但有以下特殊约束：
- 路径中不能连续经过三个相同颜色的节点
- 某些节点存在必须访问的前置节点条件
- 总节点数N ≤ 1000，边数M ≤ 10000
2.2 解题思路拆解
这道题看似是标准Dijkstra算法的变种，实则需要在状态设计中融入多重约束条件。我的解决步骤如下：
状态设计扩展：
- 传统Dijkstra使用(dist, node)二元组
- 本题需要扩展为(dist, node, prev_color, color_count)四元组
- 其中color_count记录当前相同颜色的连续出现次数
优先级队列处理：
import heapq def shortest_path(graph, start, end): heap = [] # (distance, node, prev_color, consecutive_count) heapq.heappush(heap, (0, start, None, 0)) distances = {} while heap: current_dist, u, prev_color, count = heapq.heappop(heap) if u == end: return current_dist for v, color, weight in graph[u]: new_count = count + 1 if color == prev_color else 1 if new_count > 2: continue new_dist = current_dist + weight if (v, color, new_count) not in distances or new_dist < distances[(v, color, new_count)]: distances[(v, color, new_count)] = new_dist heapq.heappush(heap, (new_dist, v, color, new_count)) return -1- 前置条件处理：
- 建立依赖关系图，先检查可达性
- 在状态转移时检查是否满足所有前置条件
2.3 时间分配与调试
- 读题分析：8分钟
- 算法设计：15分钟
- 编码实现：20分钟
- 边界测试：7分钟
踩坑警示：最初我忽略了颜色约束可能影响前置条件的检查顺序，导致部分用例失败。后来增加了状态转移时的条件校验才通过所有测试。
3. 题目二：时间序列异常检测
3.1 问题背景
给定一个金融时间序列数据，要求检测出所有异常点并给出置信度评分。数据特点：
- 高频交易数据（1分钟级别）
- 存在已知的周期性模式
- 要求在线算法（单次扫描）
3.2 解决方案设计
采用滑动窗口+统计建模的混合方法：
特征工程：
- 滑动窗口均值/标准差（窗口大小=30分钟）
- 与昨日同期数据的差值
- 波动率变化率
异常评分模型：
import numpy as np from collections import deque class AnomalyDetector: def __init__(self, window_size=30): self.window = deque(maxlen=window_size) self.ref_data = load_historical_patterns() def update(self, price, timestamp): # 计算窗口统计量 self.window.append(price) mean = np.mean(self.window) std = np.std(self.window) # 获取历史参考 time_key = timestamp.time() hist_mean = self.ref_data[time_key]['mean'] hist_std = self.ref_data[time_key]['std'] # 计算异常分数 deviation = abs(price - mean) / std hist_deviation = abs(price - hist_mean) / hist_std score = 0.7*deviation + 0.3*hist_deviation return score > 3.0, score- 参数调优：
- 通过网格搜索确定最佳权重组合
- 使用过去3个月数据作为参考基准
3.3 性能优化技巧
- 使用环形缓冲区实现滑动窗口
- 预计算历史数据的统计量
- 采用指数移动平均减少计算量
4. 题目三：期权定价优化
4.1 问题描述
实现一个美式期权定价算法，要求：
- 支持多种标的资产
- 计算速度优于标准二叉树方法
- 精度误差控制在1%以内
4.2 算法选型对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用性 |
|---|---|---|---|
| 二叉树 | O(N²) | O(N²) | 通用 |
| 三叉树 | O(N³) | O(N³) | 高精度 |
| LSMC | O(MN) | O(N) | 美式期权 |
| FDM | O(N²) | O(N) | 低维问题 |
最终选择最小二乘蒙特卡洛(LSMC)方法：
- 基础实现：
import numpy as np from sklearn.linear_model import LinearRegression def lsmc_option_price(S0, K, T, r, sigma, N=10000, M=100): dt = T/M # 生成路径 paths = np.zeros((N, M+1)) paths[:,0] = S0 for t in range(1, M+1): z = np.random.normal(size=N) paths[:,t] = paths[:,t-1] * np.exp((r-0.5*sigma**2)*dt + sigma*np.sqrt(dt)*z) # 逆向计算 payoff = np.maximum(K - paths[:,-1], 0) for t in range(M-1, 0, -1): in_the_money = paths[:,t] < K X = paths[in_the_money, t].reshape(-1,1) Y = payoff[in_the_money] * np.exp(-r*dt) model = LinearRegression() model.fit(X, Y) continuation = model.predict(X) exercise = K - X.flatten() payoff[in_the_money] = np.where(exercise > continuation, exercise, payoff[in_the_money]*np.exp(-r*dt)) return np.mean(payoff * np.exp(-r*dt))- 关键优化：
- 使用Antithetic Variates减少方差
- 采用提前终止策略
- 并行化路径计算
4.3 精度验证方法
- 与Black-Scholes结果对比（欧式期权）
- 蒙特卡洛标准误差计算
- 网格收敛性测试
5. 面试时间线全记录
5.1 申请流程节点
- 网申提交：2023-09-01
- OA邀请邮件：2023-09-15
- 完成OA：2023-09-17
- 技术面邀请：2023-09-25
5.2 OA各阶段耗时
| 阶段 | 实际耗时 | 建议耗时 |
|---|---|---|
| 环境检查 | 5分钟 | ≤5分钟 |
| 第一题 | 50分钟 | 45分钟 |
| 第二题 | 55分钟 | 50分钟 |
| 第三题 | 40分钟 | 50分钟 |
| 代码复审 | 10分钟 | 必须保留 |
经验之谈：我提前10分钟完成所有题目，这10分钟用来系统性地检查边界条件，最终发现了2处潜在bug。建议无论如何都要保留至少5分钟做全面检查。
6. 高频踩坑点及预防措施
6.1 算法设计误区
过度优化陷阱：
- 现象：一开始就追求最优解
- 对策：先实现暴力解法，再逐步优化
约束条件遗漏：
- 现象：只处理了主要约束
- 对策：用checklist列出所有条件
6.2 代码实现问题
离线测试不足：
- 现象：依赖在线测试系统
- 对策：本地构建完整测试用例集
变量命名混乱：
- 现象：临时变量过多
- 对策：坚持描述性命名规范
6.3 时间管理失误
单题耗时过长：
- 现象：在某题上花费70%时间
- 对策：设置硬性时间限制（如45分钟）
调试时间不足：
- 现象：最后时刻才发现逻辑错误
- 对策：每完成一个模块就立即测试
7. 后续准备建议
通过OA后，Two Sigma的后续面试通常会深入考察：
系统设计能力：
- 分布式计算框架
- 低延迟交易系统
数学基础：
- 随机过程
- 数值优化方法
领域知识：
- 量化交易策略
- 风险管理模型
建议准备期间重点复习：
- 《Algorithmic Trading》
- 《Options, Futures and Other Derivatives》
- 《Advances in Financial Machine Learning》
我在技术面中被问到了一个有趣的衍生问题：如何将第二题的异常检测算法实现在FPGA上以获得纳秒级延迟？这需要同时掌握算法优化和硬件加速知识。量化领域的面试往往需要这种跨学科的思维灵活性。
