Coding interview 的数据结构与算法学习 cheatsheets
面向 coding interview 的学习指南，聚焦数据结构与算法，含练习题、技巧、时间复杂度与推荐资源
这是什么
本部分深入讲解在 algorithm interviews 中高频出现的数据结构与算法的实用知识与技巧。你的工具箱越丰富，通过面试的概率越高。这些技巧还能帮你发现容易忽略的 corner cases，甚至引导你找到最优解。
每个学习指南包含什么
每个 topic 里通常会包含：
- 简短概览
- 学习资源
- 语言相关的常用库
- 时间复杂度 cheatsheet
- 面试中需要注意的点
- Corner cases
- 实用技巧 + 推荐练习题
学习指南列表
以下是 coding interview 常见数据结构/算法及对应学习指南：
| Topic | Priority |
|---|---|
| Array | High |
| String | High |
| Hash Table | Mid |
| Recursion | Mid |
| Sorting and searching | High |
| Matrix | High |
| Linked List | Mid |
| Queue | Mid |
| Stack | Mid |
| Tree | High |
| Graph | High |
| Heap | Mid |
| Trie | Mid |
| Interval | Mid |
| Dynamic programming | Low |
| Binary | Low |
| Math | Low |
| Geometry | Low |
通用面试技巧
澄清你下意识的假设。很多题目是故意不写完整的。
先验证输入。检查 invalid/empty/negative/不同类型的输入。不要默认输入一定合法。也可以直接问面试官能否假设输入合法（通常可以），以节省写校验的时间。
是否有 time/space complexity 的要求或限制？
注意 off-by-one 错误。
在没有自动类型转换的语言里，拼接时要确认类型一致：int/str/list。
写完代码后，用几个示例 input 测试你的解法。
算法是否会被多次调用（例如 web server 场景）？如果是，输入可能可以预处理以提升每次调用效率。
在函数式与命令式之间取得平衡：
- 尽量写 pure functions。
- Pure functions 更易推理，也更少 bug。
- 避免修改函数参数（尤其是引用传递），除非你非常确定。
- 但函数式通常更耗空间（因为不修改对象、不断分配新对象）。命令式更快，因为直接操作已有对象。需要在正确性与效率间找到平衡。
- 避免依赖或修改全局变量。全局变量引入状态。
- 如果必须用全局变量，确保不要意外修改。
要提升程序速度，通常有两种方式：(1) 选择更合适的数据结构/算法；(2) 用更多内存。后者是经典的 space vs time tradeoff，但并非总是以空间换速度。有时存在理论上限，无法再更快。例如在无序数组找最小值，复杂度不可能快于 O(N)。
数据结构是你的武器。选对武器才能赢。熟悉每种数据结构的优势与各操作的复杂度。
数据结构也可以组合增强。例如 hash map + doubly-linked list 可在 LRU cache 中实现 get 与 put 都是 O(1)。
Hash table 是算法题最常见的数据结构。如果你卡住了，可以列举常见数据结构并逐个思考是否可用。这一招有时很有效。
如果你在代码里“偷懒”，记得当场讲清楚，并说明非面试场景会怎么做。例如：“我会用 regex 解析这个字符串，而不是 split()，因为 split() 可能覆盖不了所有情况。”