刚拿到 Optiver SDE offer，心情是真的激动。复盘下来，整个流程一气呵成，但难度真不是一般的算法面能比的。如果你也在冲量化 / HFT 岗位，一定要看完这篇。
Optiver SDE 真题分享
Question 1
Given an array of integers where each element represents the price of a given stock on day i, design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
解法分析：
这是典型的“股票买卖问题”的进阶版，也是动态规划在面试中最常考的应用之一。
如果只允许一次交易，问题相对简单：找到最低买入点和最高卖出点即可。但当允许两次交易后，关键难点在于——两次交易不能重叠。
暴力解法是遍历所有分割点，将数组分成左右两部分，分别计算最大利润再相加，时间复杂度为 O(n²)，在 HFT 面试场景下显然不够高效。
最优解法使用动态规划，只需 一次遍历（O(n) 时间，O(1) 空间）。
核心是维护四个状态变量：
first_buy：第一次买入后的最大利润（初始为负无穷）first_sell：第一次卖出后的最大利润second_buy：第二次买入后的最大利润second_sell：第二次卖出后的最大利润
在遍历过程中，每天的价格都会更新这四个状态：
first_buy = max(first_buy, -price)
first_sell = max(first_sell, first_buy + price)
second_buy = max(second_buy, first_sell - price)
second_sell = max(second_sell, second_buy + price)
最终答案即为 second_sell。
这类题不仅考察算法思维，更是对你是否能抽象出状态转移逻辑的直接检验。
Question 2
Implement Dijkstra’s shortest-path algorithm for a weighted graph that’s supplied as a nested-dictionary adjacency map. The function should return both the distance map and each node’s previous pointer for path reconstruction.
解法分析：
Dijkstra 算法是图论中最基础也最实用的算法之一，但在高频面试中，考察重点往往不是“你记不记得算法”，而是你能否高效实现。
常规实现容易写成 O(V²)，而面试中更希望看到你使用 优先队列（heapq） 的版本，将复杂度降到 O(E log V)。
实现步骤清晰：
- 初始化距离字典
dist，所有节点为无穷大，源点为 0； - 初始化前驱字典
prev，记录路径回溯信息； - 使用
heapq存储(distance, node)，每次弹出距离最小的节点； - 对于每个相邻节点，若
dist[u] + weight(u,v) < dist[v]，则更新并压入堆。
重点在于：
- 要解释为什么优先队列能保证最短路径正确性；
- 要能写出简洁的 Python 实现；
- 若是 HFT / Infra 面试，可顺带讨论如何在 C++ 中手写堆结构来进一步优化性能。
Question 3
How can you rotate an n x n matrix 90 degrees clockwise in-place, given only a basic Python list-of-lists representation?
解法分析：
关键词是 “in-place”，即不允许额外矩阵，空间复杂度必须为 O(1)。
这个题其实考察的是你对矩阵内存布局和操作顺序的理解。
最常见的解法分两步：
- 先转置（transpose）矩阵：交换
matrix[i][j]和matrix[j][i]； - 再翻转每一行（reverse each row）。
这两步的组合实现了顺时针 90° 旋转。
如果面试官进一步追问“有没有更底层、更原子的做法”，可以提出分层旋转法：
将矩阵看作由同心的“环（layer）”组成，从外层到内层逐步旋转，每次进行 4 元素循环交换。
这个思路不仅展示了你对空间操作的灵活理解，也体现出写算法时的思维条理性。
Question 4
Explain why iterating through a 2D array column-wise is often significantly slower than iterating row-wise. Provide a C++ code example to illustrate and explain the role of cache lines.
解法分析：
这道题是 HFT / 系统类面试的常见“底层性能陷阱题”。
表面看只是二维数组的遍历顺序问题，实则考察你是否理解 CPU cache 的空间局部性原理。
当 CPU 读取内存数据时，不是只取一个变量，而是取一整块连续的内存（称为一个 cache line，通常为 64 字节）。
假设 int 占 4 字节，一个 cache line 可装下 16 个连续的 int。
按行遍历时
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += arr[i][j];
访问的内存连续，CPU 一次加载一整行到 cache，后续访问命中率极高，性能最佳。
按列遍历时：
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += arr[i][j];
每次跳跃一整行的距离，导致频繁 cache miss，需要不断从主存加载新的 cache line，性能显著下降。
在系统或高频交易类岗位中，这类题的背后考察是：
你是否理解“硬件为算法服务”的设计哲学。
Offer 到手那一刻
Optiver 的流程很快，从 OA 到拿 offer 不到两周。能拿下真的不容易。这场面试让我重新认识了“代码性能”的意义——不是写出能跑的代码，而是写出能在微秒级场景下依旧稳定的代码。
所以，如果你目标是 Optiver、Jane Street、IMC、HRT 这种高频交易公司，一定要补齐以下模块：
- C++ 底层机制（STL源码、内存模型）
- 多线程与锁机制（尤其是condition variable）
- CPU缓存、cache miss原理
- 高性能算法思维
最后一点感悟
这类面试，靠刷题真的不够。它更像是一场综合能力考试：考你理解速度、代码质量、底层思维和实时反应力。
我准备时也踩了很多坑——卡在复杂度、锁机制、缓存优化上。后来请了助教远程语音陪练，在面试节奏上稳了太多。尤其那种卡在算法临界点时的实时语音提醒，对节奏帮助特别大。
如果你也在准备 Optiver、Jane Street、IMC、HRT 这些高性能/量化公司，可以考虑找专业的辅导团队做模拟面或语音助攻。像我们 programhelp 就有针对 HFT 岗的全程远程助攻，从 OA 到 onsite 都能做到无痕、实时、节奏感极强的配合，不少同学靠这个顺利拿下 offer。
