DSA面试题

你已经刷了几百道题，却还是觉得没准备好，这通常说明你练习的是错误的那一半。本节说明面试到底在考查什么，让练习方向对上。

一场实时的数据结构与算法面试会同时考查四件事：你能否识别题目属于哪种模式、你能否在写代码前说清思路、实现在边界情况下是否正确，以及你能否口头分析复杂度。很多候选人只优化第三点、忽略第二点，结果一个正确却没有解释的答案反而被扣分。

识别这一步，正是模式练习胜过刷题数量的原因。题目很少是全新的，大多是已知模式的组合。一旦你能在头一分钟内说出这是在频率映射表上做滑动窗口，剩下的就只是执行。按语言和岗位划分的相关题库见面试问题库。

这些模式覆盖了大部分常见考题。要学会识别指向每种模式的信号。

• 双指针。有序输入、两数之和、原地分区、回文判断。
• 滑动窗口。在约束条件下求最长或最短的连续子数组。
• 哈希表计数。字母异位词、重复元素、频率比较、第一个不重复元素。
• 二分查找。有序数组，以及数组无序时在答案空间上做二分。
• 广度优先与深度优先搜索。树、网格、连通分量、无权最短路径。
• 堆与优先队列。前 k 个问题、合并有序数据流、动态求中位数。
• 区间问题。按起点排序后进行合并、插入和重叠检测。
• 动态规划。重叠子问题：爬楼梯、零钱兑换、编辑距离、子序列问题。
• 回溯。排列、组合、子集、约束类谜题。
• 图算法。拓扑排序、并查集、带权最短路径。

以下是面试官常用措辞给出的代表性题目：

• 在数组中找到两个和为目标值的数，然后不使用额外空间实现。
• 返回不含重复字符的最长子串的长度。
• 给定一个旋转排序数组，在对数时间内找到目标值。
• 合并重叠区间，并说明为什么排序这一步是值得的。
• 翻转一棵二叉树，然后求出它的最大深度。
• 验证一棵二叉搜索树，并说明简单粗暴的检查会漏掉什么。
• 统计网格中岛屿的数量，然后说明当网格大到内存放不下时该如何处理。
• 找出出现频率最高的 k 个元素，并说明你选择该数据结构的理由。
• 计算凑出某个金额所需的最少硬币数，并写出递推式。
• 检测链表中是否存在环，然后返回环的起始节点。
• 对一棵二叉树进行序列化与反序列化。
• 给定课程的先修关系，判断该课程安排是否可行。

一位应聘后端岗位的应届生拿到子串问题后立刻开始敲代码。代码几乎是对的，但面试官整场都在追问这段代码在做什么，最终的评分反映的是这份沉默，而不是那个小 bug。而另一位候选人花四十秒说出在字符映射表上滑动窗口，遇到重复就收缩左边界，同时记录最大值，就已经通过了最难挽回的那部分。

默默解题会养成错误的条件反射。实时面试要求你同时讲解和写代码，这是一项独立于两者之一的技能。

要改变的是练习方式，而不是题目本身。动笔之前，先口头说出模式、思路和预期复杂度。写代码的同时继续讲解。写完后再说一遍复杂度，并说出一个你已经处理的边界情况和一个你会向面试官确认的边界情况。用这种方式练十道题，比默默刷五十道题更能提升面试能力。

一场模拟面试会为你提供追问环节——这是无法单独练习的部分，还会给你留下自己讲解过程的录音以供回顾。这里有一条始终成立的诚实限制：带监考的浏览器内打字编程测试不是对话，任何实时助手都不该出现在其中。面试类型汇总说明了哪些编程形式是实时的，哪些是自动评测的。