第 3 章 数据结构与算法：高频问题
本章重点：排序、哈希、树、图是微服务面试中手写代码的重灾区。面试官不仅考察实现正确性，更关注复杂度分析、边界处理与工程优化能力。大厂倾向在 20 分钟内完成一道中等难度题，并追问优化路径。
📌 面试问题 1：快速排序
| 面试官考察点 | 分治思想理解、原地排序、平均/最差时间复杂度、稳定性认知、工程优化意识。 |
| 回答框架 | 1️⃣ 选 pivot → 2️⃣ 分区（双指针交换）→ 3️⃣ 递归左右子数组 → 4️⃣ 复杂度 O(n log n) / O(n²)。 |
| 简短示例回答 | “快速排序采用分治策略，随机选择 pivot 后通过 hoare 分区将数组分为小于和大于 pivot 两部分，平均时间复杂度 O(n log n)，最差 O(n²)（有序时）。手写时注意边界判断和递归深度。” |
| 可能追问 | • 如何避免最差情况？ • 快速排序是否稳定？ • 与 std::sort 的差异？ • 工程中何时改用插入排序？ |
| 避坑提醒 | ⚠️ 分区时指针移动条件易写错导致死循环；必须考虑相等元素处理；递归栈溢出需转为迭代或尾递归优化。 |
📌 面试问题 2：手写哈希表（链地址法）
| 面试官考察点 | 哈希函数设计、冲突解决（链地址 vs 开放地址）、扩容 rehash、负载因子、C++ 内存管理。 |
| 回答框架 | 1️⃣ 定义桶数组（vector<list>）→ 2️⃣ 哈希函数取模 → 3️⃣ insert/search/delete → 4️⃣ 负载因子 >0.75 时扩容 ×2 并 rehash。 |
| 简短示例回答 | “哈希表核心是数组+链表，用 std::hash 取模定位桶，冲突时头插。插入 O(1) 平均，最差 O(n)。实现时注意迭代器失效和异常安全，扩容时重新分配所有元素。” |
| 可能追问 | • 为什么链表不直接用 vector？ • 如何优化缓存行？ • 开放地址法优缺点？ • C++ 中 std::unordered_map 如何实现？ |
| 避坑提醒 | ⚠️ 忘记重载哈希函数导致编译错误；扩容时原迭代器失效；负载因子过高引发性能雪崩。 |
📌 面试问题 3：二叉树最近公共祖先（LCA）
| 面试官考察点 | 递归理解、后序遍历、BST 优化、二叉搜索树性质利用、空间复杂度。 |
| 回答框架 | 1️⃣ 递归后序遍历 → 2️⃣ 左子树含 p 返回左，右子树含 q 返回右 → 3️⃣ 若左右均非空，当前节点即 LCA → 4️⃣ BST 版本按值比较大小决定方向。 |
| 简短示例回答 | “对普通二叉树使用 DFS 后序递归：查找 p 或 q，如果左右子树均找到则当前节点为 LCA。时间复杂度 O(n)，空间 O(h)。若为 BST，利用节点值特性可降至 O(log n)。” |
| 可能追问 | • 如果节点可能不存在？ • 如何实现非递归版本？ • 如何处理多个节点 LCA？ • 深度与节点数关系？ |
| 避坑提醒 | ⚠️ 递归时未正确传递 bool 返回值；未处理空树或单节点；BST 版本忽略值相等的情况。 |
🧠 高频算法复杂度速查表
| 算法类别 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 | 手写频率 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 | ★★★★★ |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | ★★★★☆ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | ★★★★☆ |
| 二分查找 | O(log n) | O(log n) | O(1) | — | ★★★★☆ |
| 哈希表（链地址） | O(1) 均摊 | O(n) | O(n) | — | ★★★★★ |
| 二叉树遍历 | O(n) | O(n) | O(h) | — | ★★★★☆ |
| 图 DFS / BFS | O(V+E) | O(V+E) | O(V) | — | ★★★★☆ |
💡 加分项提示：回答任何算法题时，主动先问输入规模（数据量）、是否允许额外空间；手写代码后补充测试用例（空、单元素、重复元素、大数据）。大厂面试官看重“能写出 bug‑free 生产级代码”的习惯。