小米2019秋招算法笔试题B这套卷子我前前后后刷了三遍。第一遍是照着网上的回忆版硬做卡在 KMP 的 next 数组上第二遍是整理考点发现它几乎把算法笔试最核心的模块都覆盖了第三遍再刷已经是拿它当面试前的自测清单用了。如果你正在准备算法岗的秋招或春招或者只是想看看自己的算法基本功有没有退化这套题都值得认真过一遍。先说结论这套 B 卷放在当年大厂笔试里难度不算最变态但很“小米”——不追求偏题怪题更看重基础是否扎实、代码是否干净。题型大致是选择、填空、编程题混合覆盖了字符串匹配、排序、动态规划、贪心、图论这几大块。网上热词里反复出现的 KMP、堆排序、Dijkstra、贪心算法基本就是当年考场上的真实画风。1. 先看全局B卷的考点分布与命题风格1.1 题型结构与时间分配2019 年小米秋招算法 B 卷并没有公开的官方版本现在能看到的都是考过的同学回忆出来的题。我根据回忆版和自己的考场经验把结构整理成了一张参考表。具体题号可能记不准确但考察范围基本是确定的。题型题量参考主要考察内容推荐用时选择题10 - 15 道数据结构、复杂度、排序稳定性、图论概念20 - 30 分钟填空题5 - 8 道KMP next 数组、递推式、概率计算、手算复杂度20 分钟左右编程题2 - 4 道动态规划、贪心、搜索、字符串处理60 - 80 分钟简答题0 - 1 道算法设计思路、复杂度优化方案10 分钟左右这个时间分配是我自己模拟考的时候验证过的。选择题和填空题看着分少但特别拉分因为算法岗的简历初筛很看重笔试成绩一道概念题错了可能就掉一个档。编程题是主战场但不宜死磕某一题卡了 15 分钟还没思路就先跳过把能拿的分都拿了再回来。1.2 高频考点画像我复盘的时候把高频考点和网上的算法热词做了个对照B 卷真正想筛的其实就是下面这几块考点方向常见热词命中的原因字符串匹配KMP、AC 自动机、BM25字符串题最见基本功next 数组计算非常适合出填空排序算法快排、堆排、归并、冒泡复杂度、稳定性、手写代码全是选择题素材动态规划背包、编辑距离、LIS区分度大是编程题主力图论Dijkstra、拓扑排序、二分图少数人真正掌握用来拉差距数学快速幂、最大公约数、贪心代码短、坑多特别能考察细节粒子群算法、模拟退火这类智能优化算法偶尔也会出现在选择或判断题里但通常只是让你判断“哪个属于确定性算法”或者“哪个不适用于离散优化”属于扩展知识。B 卷的主旋律还是经典数据结构和通用算法所以备考重心不用放在那些花哨的名词上。2. 核心考点深度拆解2.1 KMP 的 next 数组到底怎么算KMP 算法是整套 B 卷里最出名的一道题因为网上讨论最多的就是“模式串 pabacaba 的 next 数组是多少”。这个考点看起来简单但它同时考察了三层能力懂不懂前缀和后缀的概念、能不能手算、能不能用代码递推出来。先明确一个基础定义。对于模式串的一个前缀子串它的最长相等真前后缀长度指的是这个子串中既是前缀又是后缀、且长度小于子串本身的最长部分的长度。比如子串abab前缀有a, ab, aba后缀有b, ab, bab最长公共前后缀是ab长度是 2。对于pabacaba我们逐位算一下最长相等真前后缀长度下标 i当前前缀最长相等真前后缀长度0a无01ab无02abaa13abac无04abacaa15abacabab26abacabaaba3这里就引出了很多同学栽跟头的地方next 数组有两种常见定义。一种是“前缀函数数组”记作 pi[i]直接存上面表格里的最长相等真前后缀长度另一种是“失配跳转数组”表示第 i 位失配时应该跳到哪个位置继续匹配。这两种定义在笔试题里都出现过如果题目没有给明确公式一定要先看它要求的是哪一个。如果题目要求的是“第 i 位失配时跳到 next[i]”其中 next[0] -1那么pabacaba的 next 数组应该是next [-1, 0, 0, 1, 0, 1, 2]这个结果怎么来的把上一张表的长度往右移动一位空出来的 next[0] 填 -1 就行。next[1] 对应 pi[0]0next[2] 对应 pi[1]0next[3] 对应 pi[2]1以此类推。如果题目下标从 1 开始那么可能写成[0, 0, 0, 1, 0, 1, 2]。所以做题之前先看下标习惯别把所有版本混在一起。提示KMP next 数组题最容易犯的错误不是不会算最长前后缀而是不清楚题目用的是前缀函数还是失配跳转。拿到题先看定义再动手。2.2 排序算法复杂度与稳定性是选择题重灾区排序算法在笔试里的地位非常稳定几乎必考。因为一个排序问题可以延伸出很多维度时间复杂度、空间复杂度、是否稳定、是否原地排序、最好最坏情况、比较次数、适合数据规模等等。选择题想拉开差距出排序是最划算的。我当时整理的速查表是这样的算法平均时间复杂度最坏复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定笔试里快速排序的出现频率最高因为代码短但细节多。小米 B 卷有一道选择题印象很深“快速排序在什么情况下退化到 O(n²)”答案是当每次 partition 选到的 pivot 都恰好是当前区间最小或最大值时比如对已经有序的数组固定取第一个元素作为 pivot。这个点本身不难但很多人只记得平均复杂度忽略了退化条件。另外堆排序和归并排序也常被用来考察“稳定性”这个概念。很多前端或者客户端方向的候选人容易混淆因为 JavaScript 的Array.prototype.sort()在不同引擎里的稳定性都不一样。笔试题基本都是基于经典教材的定义别拿工程实践来杠。手写排序算法是编程题的一个备选项我后面会单独拿一节来讲快排的完整写法。2.3 动态规划先定状态再写转移B 卷的编程题里动态规划的出镜率极高。小米的算法岗笔试不可能不考 DP因为 DP 最能看一个人的逻辑归纳能力。我复盘时遇到最有代表性的一个题是最长上升子序列LIS。题目很简单给定一个无序整数数组找最长严格递增子序列的长度。比如[10, 9, 2, 5, 3, 7, 101, 18]的答案是 4对应[2, 3, 7, 101]。DP 的第一步是定义状态。定义dp[i]表示以nums[i]结尾的最长上升子序列长度。这里的关键词是“以 nums[i] 结尾”因为只有确定了结尾才能判断下一个元素能不能接上去。第二步是初始化。每个元素都可以独自成为一个子序列所以dp[i]初始为 1。第三步是转移方程。对于每个i遍历它前面所有j i如果nums[j] nums[i]说明nums[i]可以接在以nums[j]结尾的子序列后面此时dp[i] max(dp[i], dp[j] 1)。最后答案就是dp数组的最大值。def lengthOfLIS(nums): n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n 0 else 0这个解法的时间复杂度是 O(n²)在 n 不大的情况下够用。如果 n 到 10⁵就必须用贪心加二分优化成 O(n log n)。这个优化思路叫“耐心排序”维护一个 tails 数组tails[k]表示长度为 k1 的上升子序列的最小末尾值然后对每个元素二分查找它的插入位置。写法不一样但背后的状态含义更抽象。笔试时如果时间允许建议先写 O(n²) 版因为不容易错如果明确给了大数据范围再写二分优化版。2.4 贪心与图论从“看起来对”到“证明对”贪心算法的题在 B 卷里往往以中等难度出现最经典的模型是区间问题。比如“给定一系列区间选出尽量多的互不重叠区间”或者“用最少的点覆盖所有区间”。这类题的共同点是先排序再按某种策略逐个决策。以“最多互不重叠区间”为例正确策略是按照区间结束时间从小到大排序然后依次选择第一个结束的区间再跳过所有与它重叠的区间。这个策略的直观解释是结束得越早后面能留下的空间越大所以越可能选到更多区间。笔试里除了写出代码还要能说清楚“为什么贪心策略是对的”这在简答题里很加分。图论部分B 卷经常涉及 Dijkstra 和拓扑排序。Dijkstra 考得最多的是一个判断题“Dijkstra 算法为什么不能处理负权边”标准回答是Dijkstra 每轮从当前未访问的点中选一个距离最小的点把它当成已确定最短路的点这个“已确定”依赖当前距离已经是最小值如果存在负权边后面可能出现“通过负权边达到更小距离”的情况但这个点已经被标记完成了无法再更新。记忆方法就是Dijkstra 本质是贪心贪心的前提是局部最优等于全局最优负权边会破坏这个前提。拓扑排序也有一个经典实现套路叫做 Kahn 算法。维护一个入度表先把所有入度为 0 的点入队然后逐个出队每出队一个点就把和它相邻的点入度减 1如果某个相邻点入度变成 0就继续入队。队列为空时如果访问过的点数不等于总点数说明图里有环。def topoSort(n, edges): from collections import deque indeg [0] * n graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) indeg[v] 1 q deque([i for i in range(n) if indeg[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) return res if len(res) n else []如果返回空列表说明存在环。这段代码在笔试中的通过率很高因为逻辑固定不太需要现场发挥但前提是你真的理解了入度表的含义。3. 实战复盘高频题手写全过程3.1 手写快排从递归到边界处理快排在小米 B 卷里既可能出现在选择题也可能出现在编程题第一题。我建议所有人把快排背成肌肉记忆因为它是很多复杂算法的底子比如 Top-K 问题可以用快排的 partition 思想做部分排序。我常用的快排实现是双指针版本void quickSort(vectorint nums, int left, int right) { if (left right) return; // 空区间或单元素直接返回 int i left, j right; int pivot nums[(left right) / 2]; // 取中间元素作基准 while (i j) { while (nums[i] pivot) i; // 左边找大于等于 pivot 的值 while (nums[j] pivot) j--; // 右边找小于等于 pivot 的值 if (i j) { swap(nums[i], nums[j]); i; j--; } } quickSort(nums, left, j); quickSort(nums, i, right); }这里有两个细节容易犯错。第一pivot 不要固定取nums[left]否则遇到已经有序的数组会退化到 O(n²)取中间元素能在绝大多数情况下避免这个坑。第二循环条件是while (i j)而不是while (i j)因为这样才能保证分区后左边和右边都严格小于原区间不会出现无限递归。我见过很多人在这个条件上写错递归栈溢出直接白给。如果笔试环境不支持递归可以改成显式栈模拟递归但一般情况下 Java 和 C 的递归深度足够处理 10⁵ 的数据不需要自己实现栈。3.2 KMP next 数组现场计算演示前面已经讲了手算 next 数组这里再补一个代码版本。如果题目要你写一个函数来计算 next 数组最稳妥的方式是用前缀函数思想递推vectorint buildNext(const string p) { int m p.size(); vectorint pi(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } return pi; }这段代码算出来的是前缀函数pi。如果你要的是失配跳转数组还需要把pi整体右移一位next[0] -1。具体到这个题目模式串pabacaba算出来的pi是[0, 0, 1, 0, 1, 2, 3]右移后得到[-1, 0, 0, 1, 0, 1, 2]。这一步在很多题解里没有写清楚但恰恰是考试最容易丢分的地方。3.3 编辑距离的两种写法编辑距离是 DP 题里另一个高频面孔。题目描述是给两个字符串 word1 和 word2允许插入、删除、替换三种操作求把 word1 变成 word2 的最少操作次数。状态定义是dp[i][j]表示word1前 i 个字符变成word2前 j 个字符需要的最少操作数。初始化dp[i][0] i因为要把一个长度为 i 的字符串变成空串只能删除 i 次同理dp[0][j] j。转移方程考虑三种操作删除dp[i-1][j] 1插入dp[i][j-1] 1替换如果word1[i-1] word2[j-1]则dp[i-1][j-1]否则dp[i-1][j-1] 1取三者最小值。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]由于每一行只依赖上一行和当前行可以用两个一维数组滚动更新把空间复杂度从 O(mn) 降到 O(n)。笔试时如果没要求优化先写二维版本因为编码更直接不容易漏初始化。3.4 贪心小题区间选点B 卷的贪心题很可能给一个具体场景比如“有一些课程每门课有开始时间和结束时间选尽可能多的课程不能冲突”。这就是经典的区间调度问题直接用贪心。def intervalSchedule(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count按结束时间排序是这类问题的通用解法。关键是为什么不能按开始时间排序因为一个开始早的区间可能很长会挡住后面很多区间而结束时间越早给后面留下的空间越大。这种反例在考试中一定要会举比如区间[1, 100]和[2, 3]、[4, 5]如果按开始时间排序选了[1, 100]就只能选 1 个而按结束时间排序可以选 2 个。4. 刷题血泪史笔试里的常见坑与排查技巧4.1 next 数组定义不清导致功亏一篑这个坑我栽过而且是实实在在在模拟笔试里栽的。当时题目写的是next[i]定义为“当第 i 位失配时模式串跳转到的位置”但我脑子里默认用了前缀函数的定义结果填出来的数组完全对不上。后来我发现很多培训机构讲 KMP 时用的是“最长相等前后缀长度”作为 next 值而考研教材和互联网笔试题又常常用“失配跳转位置”作为 next 值。两种定义之间只差一个右移但题目不会告诉你它用的是哪种。我的建议是考场上看到 next 数组题先看题目有没有给出定义公式。如果给了严格按照公式算如果没给优先采用失配跳转位置的定义也就是next[0] -1或next[1] 0的版本因为这是大厂笔试最常见的写法。同时为了保险可以把两种定义都写在草稿纸上对比一下再填答案。4.2 数据范围决定算法选型算法笔试里最难受的不是不会做而是“我明明写出了正确代码但超时”。小米 B 卷的编程题不会明着告诉你数据范围但它会在题目描述里给一些隐含线索比如“数组长度不超过 10⁵”。看到这个量级基本可以排除 O(n²) 的暴力解法应该直接往 O(n log n) 或 O(n) 方向想。我自己的习惯是拿到题目先看数据范围心里估算一下。10³ 以内可以用 O(n²)10⁵ 左右要用 O(n log n)10⁶ 以上基本要 O(n) 或者接近 O(n)。动态规划题尤其要关注这一点因为 DP 的朴素写法往往就是 O(n²)。如果代码写完了突然发现复杂度不对不要慌先看能不能优化。比如最长上升子序列可以从 O(n²) 优化到 O(n log n)编辑距离可以用滚动数组优化空间快排可以用随机 pivot 优化退化情况。这些都是笔试考场上性价比很高的操作。4.3 输入输出与调试技巧在线笔试的输入输出格式和本地刷题很不一样。小米用的笔试系统当年是赛码网输入可能有多组测试用例每组之间用空行隔开。很多人不是不会做而是卡在读取数据上。经验教训是笔试前先熟悉常见输入模板。比如 C 用cin读取不知道有多少组的输入时用while (cin n)Java 用hasNext()Python 用sys.stdin按行读。另外输出格式一定要精确到空格和换行有的题要求“每个答案占一行”有的要求“答案之间用空格分隔”少一个空格就是 Wrong Answer。还有一个调试技巧本地测试时除了题目示例一定要自己造几个极端小数据尤其是空数组、单元素数组、全相等数组、最大数据范围。这些边界情况最容易暴露出代码里的隐患。我在笔试时吃过亏的是求数组最大值时初始值设为 0结果数组里全是负数答案直接错了。正确的初始值应该是nums[0]或者INT_MIN。4.4 时间分配先做编程还是先做填空这可能是因人而异的但我的建议是先做有把握的填空和选择因为它们拿分快能建立信心。KMP next 数组这种填空题只要定义看清了两分钟就能写完。然后立刻跳去做相对简单的编程题至少拿到一题的完整分数。最后把时间留给最难的 DP 或图论题。千万不要在一道编程题上死磕超过 20 分钟。因为算法岗笔试的通过标准往往不是满分而是看总排名。如果你把时间耗在一道 30% 通过率的难题上可能连基础题都来不及写。我刷这套 B 卷时做过一个测试先做编程题后做选择总分反而低了因为时间被长代码吃掉了。所以“先易后难先快后慢”是我目前最推荐的时间策略。5. 从B卷看算法面试的底层逻辑5.1 复杂度直觉比题目本身更重要这套 B 卷刷到最后我最大的感触是它并不想靠偏题怪题难倒你而是想通过经典题看你有没有“复杂度直觉”。比如看到 KMP第一反应是 O(mn) 的字符串匹配看到 LIS第一反应是 O(n log n) 可以优化看到区间调度第一反应是按结束时间排序。这个直觉不是背题背出来的而是需要大量刷题和复盘才能形成的条件反射。面试官出题的时候也一样他们看重的不是你把这道题做对了而是你分析问题的路径能不能先暴力再优化最后说清楚每种方案的复杂度和适用场景。如果你的答案里能主动说出“当数据量大时需要换一种思路”会比闷头写代码好很多。5.2 错题归因把每道错题归到知识点我整理这套 B 卷的时候做了一个简单的错题表把每道错题归到对应的知识点并标注错误原因是概念不熟、边界没考虑还是代码实现有问题。比如 KMP next 数组那道题我标的是“定义混淆”LIS 那道题我标的是“忘了考虑空数组”。这样做的好处是后续复习时不用重头再来只需要看错题表里高频出现的知识点就行。5.3 复盘模板题目、思路、复杂度、容易错点最后分享一个适合所有人的复盘模板。每做一道题不管对错都在笔记里按四栏记录题目简要描述、核心思路、复杂度、容易错点。小米这套 B 卷做完我的笔记大概长这样题目核心思路复杂度容易错点KMP next 数组最长相等真前后缀右移一位O(m)定义混淆快排双指针分区O(n log n)pivot 选第一个导致退化最长上升子序列dp[i] 表示以 i 结尾O(n²) / O(n log n)初始化遗漏区间调度按结束时间排序O(n log n)排序依据搞错这套模板用熟了之后你会发现很多题其实是在重复考同一个知识点。比如编辑距离、最长公共子序列、最长上升子序列本质上都是二维或一维 DP状态定义一换代码逻辑就很相似。把这些共同点提炼出来笔试的备考效率会提高很多。最后说个我自己的小习惯。每次笔试结束不管考得好不好我都会趁热把没写对的题重新归类写进同一个复盘文档并标上错误原因。小米这套 B 卷的 KMP 题我当时就写了四个字定义混淆。等下次再看到类似的 next 数组题我会先在草稿纸上把两种定义都列出来再动手。笔试本来就是个熟练活复盘到位了下一次才能真正避开同一个坑。
小米2019秋招算法笔试题B卷深度复盘：KMP、DP与贪心全解析
小米2019秋招算法笔试题B这套卷子我前前后后刷了三遍。第一遍是照着网上的回忆版硬做卡在 KMP 的 next 数组上第二遍是整理考点发现它几乎把算法笔试最核心的模块都覆盖了第三遍再刷已经是拿它当面试前的自测清单用了。如果你正在准备算法岗的秋招或春招或者只是想看看自己的算法基本功有没有退化这套题都值得认真过一遍。先说结论这套 B 卷放在当年大厂笔试里难度不算最变态但很“小米”——不追求偏题怪题更看重基础是否扎实、代码是否干净。题型大致是选择、填空、编程题混合覆盖了字符串匹配、排序、动态规划、贪心、图论这几大块。网上热词里反复出现的 KMP、堆排序、Dijkstra、贪心算法基本就是当年考场上的真实画风。1. 先看全局B卷的考点分布与命题风格1.1 题型结构与时间分配2019 年小米秋招算法 B 卷并没有公开的官方版本现在能看到的都是考过的同学回忆出来的题。我根据回忆版和自己的考场经验把结构整理成了一张参考表。具体题号可能记不准确但考察范围基本是确定的。题型题量参考主要考察内容推荐用时选择题10 - 15 道数据结构、复杂度、排序稳定性、图论概念20 - 30 分钟填空题5 - 8 道KMP next 数组、递推式、概率计算、手算复杂度20 分钟左右编程题2 - 4 道动态规划、贪心、搜索、字符串处理60 - 80 分钟简答题0 - 1 道算法设计思路、复杂度优化方案10 分钟左右这个时间分配是我自己模拟考的时候验证过的。选择题和填空题看着分少但特别拉分因为算法岗的简历初筛很看重笔试成绩一道概念题错了可能就掉一个档。编程题是主战场但不宜死磕某一题卡了 15 分钟还没思路就先跳过把能拿的分都拿了再回来。1.2 高频考点画像我复盘的时候把高频考点和网上的算法热词做了个对照B 卷真正想筛的其实就是下面这几块考点方向常见热词命中的原因字符串匹配KMP、AC 自动机、BM25字符串题最见基本功next 数组计算非常适合出填空排序算法快排、堆排、归并、冒泡复杂度、稳定性、手写代码全是选择题素材动态规划背包、编辑距离、LIS区分度大是编程题主力图论Dijkstra、拓扑排序、二分图少数人真正掌握用来拉差距数学快速幂、最大公约数、贪心代码短、坑多特别能考察细节粒子群算法、模拟退火这类智能优化算法偶尔也会出现在选择或判断题里但通常只是让你判断“哪个属于确定性算法”或者“哪个不适用于离散优化”属于扩展知识。B 卷的主旋律还是经典数据结构和通用算法所以备考重心不用放在那些花哨的名词上。2. 核心考点深度拆解2.1 KMP 的 next 数组到底怎么算KMP 算法是整套 B 卷里最出名的一道题因为网上讨论最多的就是“模式串 pabacaba 的 next 数组是多少”。这个考点看起来简单但它同时考察了三层能力懂不懂前缀和后缀的概念、能不能手算、能不能用代码递推出来。先明确一个基础定义。对于模式串的一个前缀子串它的最长相等真前后缀长度指的是这个子串中既是前缀又是后缀、且长度小于子串本身的最长部分的长度。比如子串abab前缀有a, ab, aba后缀有b, ab, bab最长公共前后缀是ab长度是 2。对于pabacaba我们逐位算一下最长相等真前后缀长度下标 i当前前缀最长相等真前后缀长度0a无01ab无02abaa13abac无04abacaa15abacabab26abacabaaba3这里就引出了很多同学栽跟头的地方next 数组有两种常见定义。一种是“前缀函数数组”记作 pi[i]直接存上面表格里的最长相等真前后缀长度另一种是“失配跳转数组”表示第 i 位失配时应该跳到哪个位置继续匹配。这两种定义在笔试题里都出现过如果题目没有给明确公式一定要先看它要求的是哪一个。如果题目要求的是“第 i 位失配时跳到 next[i]”其中 next[0] -1那么pabacaba的 next 数组应该是next [-1, 0, 0, 1, 0, 1, 2]这个结果怎么来的把上一张表的长度往右移动一位空出来的 next[0] 填 -1 就行。next[1] 对应 pi[0]0next[2] 对应 pi[1]0next[3] 对应 pi[2]1以此类推。如果题目下标从 1 开始那么可能写成[0, 0, 0, 1, 0, 1, 2]。所以做题之前先看下标习惯别把所有版本混在一起。提示KMP next 数组题最容易犯的错误不是不会算最长前后缀而是不清楚题目用的是前缀函数还是失配跳转。拿到题先看定义再动手。2.2 排序算法复杂度与稳定性是选择题重灾区排序算法在笔试里的地位非常稳定几乎必考。因为一个排序问题可以延伸出很多维度时间复杂度、空间复杂度、是否稳定、是否原地排序、最好最坏情况、比较次数、适合数据规模等等。选择题想拉开差距出排序是最划算的。我当时整理的速查表是这样的算法平均时间复杂度最坏复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定笔试里快速排序的出现频率最高因为代码短但细节多。小米 B 卷有一道选择题印象很深“快速排序在什么情况下退化到 O(n²)”答案是当每次 partition 选到的 pivot 都恰好是当前区间最小或最大值时比如对已经有序的数组固定取第一个元素作为 pivot。这个点本身不难但很多人只记得平均复杂度忽略了退化条件。另外堆排序和归并排序也常被用来考察“稳定性”这个概念。很多前端或者客户端方向的候选人容易混淆因为 JavaScript 的Array.prototype.sort()在不同引擎里的稳定性都不一样。笔试题基本都是基于经典教材的定义别拿工程实践来杠。手写排序算法是编程题的一个备选项我后面会单独拿一节来讲快排的完整写法。2.3 动态规划先定状态再写转移B 卷的编程题里动态规划的出镜率极高。小米的算法岗笔试不可能不考 DP因为 DP 最能看一个人的逻辑归纳能力。我复盘时遇到最有代表性的一个题是最长上升子序列LIS。题目很简单给定一个无序整数数组找最长严格递增子序列的长度。比如[10, 9, 2, 5, 3, 7, 101, 18]的答案是 4对应[2, 3, 7, 101]。DP 的第一步是定义状态。定义dp[i]表示以nums[i]结尾的最长上升子序列长度。这里的关键词是“以 nums[i] 结尾”因为只有确定了结尾才能判断下一个元素能不能接上去。第二步是初始化。每个元素都可以独自成为一个子序列所以dp[i]初始为 1。第三步是转移方程。对于每个i遍历它前面所有j i如果nums[j] nums[i]说明nums[i]可以接在以nums[j]结尾的子序列后面此时dp[i] max(dp[i], dp[j] 1)。最后答案就是dp数组的最大值。def lengthOfLIS(nums): n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n 0 else 0这个解法的时间复杂度是 O(n²)在 n 不大的情况下够用。如果 n 到 10⁵就必须用贪心加二分优化成 O(n log n)。这个优化思路叫“耐心排序”维护一个 tails 数组tails[k]表示长度为 k1 的上升子序列的最小末尾值然后对每个元素二分查找它的插入位置。写法不一样但背后的状态含义更抽象。笔试时如果时间允许建议先写 O(n²) 版因为不容易错如果明确给了大数据范围再写二分优化版。2.4 贪心与图论从“看起来对”到“证明对”贪心算法的题在 B 卷里往往以中等难度出现最经典的模型是区间问题。比如“给定一系列区间选出尽量多的互不重叠区间”或者“用最少的点覆盖所有区间”。这类题的共同点是先排序再按某种策略逐个决策。以“最多互不重叠区间”为例正确策略是按照区间结束时间从小到大排序然后依次选择第一个结束的区间再跳过所有与它重叠的区间。这个策略的直观解释是结束得越早后面能留下的空间越大所以越可能选到更多区间。笔试里除了写出代码还要能说清楚“为什么贪心策略是对的”这在简答题里很加分。图论部分B 卷经常涉及 Dijkstra 和拓扑排序。Dijkstra 考得最多的是一个判断题“Dijkstra 算法为什么不能处理负权边”标准回答是Dijkstra 每轮从当前未访问的点中选一个距离最小的点把它当成已确定最短路的点这个“已确定”依赖当前距离已经是最小值如果存在负权边后面可能出现“通过负权边达到更小距离”的情况但这个点已经被标记完成了无法再更新。记忆方法就是Dijkstra 本质是贪心贪心的前提是局部最优等于全局最优负权边会破坏这个前提。拓扑排序也有一个经典实现套路叫做 Kahn 算法。维护一个入度表先把所有入度为 0 的点入队然后逐个出队每出队一个点就把和它相邻的点入度减 1如果某个相邻点入度变成 0就继续入队。队列为空时如果访问过的点数不等于总点数说明图里有环。def topoSort(n, edges): from collections import deque indeg [0] * n graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) indeg[v] 1 q deque([i for i in range(n) if indeg[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) return res if len(res) n else []如果返回空列表说明存在环。这段代码在笔试中的通过率很高因为逻辑固定不太需要现场发挥但前提是你真的理解了入度表的含义。3. 实战复盘高频题手写全过程3.1 手写快排从递归到边界处理快排在小米 B 卷里既可能出现在选择题也可能出现在编程题第一题。我建议所有人把快排背成肌肉记忆因为它是很多复杂算法的底子比如 Top-K 问题可以用快排的 partition 思想做部分排序。我常用的快排实现是双指针版本void quickSort(vectorint nums, int left, int right) { if (left right) return; // 空区间或单元素直接返回 int i left, j right; int pivot nums[(left right) / 2]; // 取中间元素作基准 while (i j) { while (nums[i] pivot) i; // 左边找大于等于 pivot 的值 while (nums[j] pivot) j--; // 右边找小于等于 pivot 的值 if (i j) { swap(nums[i], nums[j]); i; j--; } } quickSort(nums, left, j); quickSort(nums, i, right); }这里有两个细节容易犯错。第一pivot 不要固定取nums[left]否则遇到已经有序的数组会退化到 O(n²)取中间元素能在绝大多数情况下避免这个坑。第二循环条件是while (i j)而不是while (i j)因为这样才能保证分区后左边和右边都严格小于原区间不会出现无限递归。我见过很多人在这个条件上写错递归栈溢出直接白给。如果笔试环境不支持递归可以改成显式栈模拟递归但一般情况下 Java 和 C 的递归深度足够处理 10⁵ 的数据不需要自己实现栈。3.2 KMP next 数组现场计算演示前面已经讲了手算 next 数组这里再补一个代码版本。如果题目要你写一个函数来计算 next 数组最稳妥的方式是用前缀函数思想递推vectorint buildNext(const string p) { int m p.size(); vectorint pi(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } return pi; }这段代码算出来的是前缀函数pi。如果你要的是失配跳转数组还需要把pi整体右移一位next[0] -1。具体到这个题目模式串pabacaba算出来的pi是[0, 0, 1, 0, 1, 2, 3]右移后得到[-1, 0, 0, 1, 0, 1, 2]。这一步在很多题解里没有写清楚但恰恰是考试最容易丢分的地方。3.3 编辑距离的两种写法编辑距离是 DP 题里另一个高频面孔。题目描述是给两个字符串 word1 和 word2允许插入、删除、替换三种操作求把 word1 变成 word2 的最少操作次数。状态定义是dp[i][j]表示word1前 i 个字符变成word2前 j 个字符需要的最少操作数。初始化dp[i][0] i因为要把一个长度为 i 的字符串变成空串只能删除 i 次同理dp[0][j] j。转移方程考虑三种操作删除dp[i-1][j] 1插入dp[i][j-1] 1替换如果word1[i-1] word2[j-1]则dp[i-1][j-1]否则dp[i-1][j-1] 1取三者最小值。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]由于每一行只依赖上一行和当前行可以用两个一维数组滚动更新把空间复杂度从 O(mn) 降到 O(n)。笔试时如果没要求优化先写二维版本因为编码更直接不容易漏初始化。3.4 贪心小题区间选点B 卷的贪心题很可能给一个具体场景比如“有一些课程每门课有开始时间和结束时间选尽可能多的课程不能冲突”。这就是经典的区间调度问题直接用贪心。def intervalSchedule(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count按结束时间排序是这类问题的通用解法。关键是为什么不能按开始时间排序因为一个开始早的区间可能很长会挡住后面很多区间而结束时间越早给后面留下的空间越大。这种反例在考试中一定要会举比如区间[1, 100]和[2, 3]、[4, 5]如果按开始时间排序选了[1, 100]就只能选 1 个而按结束时间排序可以选 2 个。4. 刷题血泪史笔试里的常见坑与排查技巧4.1 next 数组定义不清导致功亏一篑这个坑我栽过而且是实实在在在模拟笔试里栽的。当时题目写的是next[i]定义为“当第 i 位失配时模式串跳转到的位置”但我脑子里默认用了前缀函数的定义结果填出来的数组完全对不上。后来我发现很多培训机构讲 KMP 时用的是“最长相等前后缀长度”作为 next 值而考研教材和互联网笔试题又常常用“失配跳转位置”作为 next 值。两种定义之间只差一个右移但题目不会告诉你它用的是哪种。我的建议是考场上看到 next 数组题先看题目有没有给出定义公式。如果给了严格按照公式算如果没给优先采用失配跳转位置的定义也就是next[0] -1或next[1] 0的版本因为这是大厂笔试最常见的写法。同时为了保险可以把两种定义都写在草稿纸上对比一下再填答案。4.2 数据范围决定算法选型算法笔试里最难受的不是不会做而是“我明明写出了正确代码但超时”。小米 B 卷的编程题不会明着告诉你数据范围但它会在题目描述里给一些隐含线索比如“数组长度不超过 10⁵”。看到这个量级基本可以排除 O(n²) 的暴力解法应该直接往 O(n log n) 或 O(n) 方向想。我自己的习惯是拿到题目先看数据范围心里估算一下。10³ 以内可以用 O(n²)10⁵ 左右要用 O(n log n)10⁶ 以上基本要 O(n) 或者接近 O(n)。动态规划题尤其要关注这一点因为 DP 的朴素写法往往就是 O(n²)。如果代码写完了突然发现复杂度不对不要慌先看能不能优化。比如最长上升子序列可以从 O(n²) 优化到 O(n log n)编辑距离可以用滚动数组优化空间快排可以用随机 pivot 优化退化情况。这些都是笔试考场上性价比很高的操作。4.3 输入输出与调试技巧在线笔试的输入输出格式和本地刷题很不一样。小米用的笔试系统当年是赛码网输入可能有多组测试用例每组之间用空行隔开。很多人不是不会做而是卡在读取数据上。经验教训是笔试前先熟悉常见输入模板。比如 C 用cin读取不知道有多少组的输入时用while (cin n)Java 用hasNext()Python 用sys.stdin按行读。另外输出格式一定要精确到空格和换行有的题要求“每个答案占一行”有的要求“答案之间用空格分隔”少一个空格就是 Wrong Answer。还有一个调试技巧本地测试时除了题目示例一定要自己造几个极端小数据尤其是空数组、单元素数组、全相等数组、最大数据范围。这些边界情况最容易暴露出代码里的隐患。我在笔试时吃过亏的是求数组最大值时初始值设为 0结果数组里全是负数答案直接错了。正确的初始值应该是nums[0]或者INT_MIN。4.4 时间分配先做编程还是先做填空这可能是因人而异的但我的建议是先做有把握的填空和选择因为它们拿分快能建立信心。KMP next 数组这种填空题只要定义看清了两分钟就能写完。然后立刻跳去做相对简单的编程题至少拿到一题的完整分数。最后把时间留给最难的 DP 或图论题。千万不要在一道编程题上死磕超过 20 分钟。因为算法岗笔试的通过标准往往不是满分而是看总排名。如果你把时间耗在一道 30% 通过率的难题上可能连基础题都来不及写。我刷这套 B 卷时做过一个测试先做编程题后做选择总分反而低了因为时间被长代码吃掉了。所以“先易后难先快后慢”是我目前最推荐的时间策略。5. 从B卷看算法面试的底层逻辑5.1 复杂度直觉比题目本身更重要这套 B 卷刷到最后我最大的感触是它并不想靠偏题怪题难倒你而是想通过经典题看你有没有“复杂度直觉”。比如看到 KMP第一反应是 O(mn) 的字符串匹配看到 LIS第一反应是 O(n log n) 可以优化看到区间调度第一反应是按结束时间排序。这个直觉不是背题背出来的而是需要大量刷题和复盘才能形成的条件反射。面试官出题的时候也一样他们看重的不是你把这道题做对了而是你分析问题的路径能不能先暴力再优化最后说清楚每种方案的复杂度和适用场景。如果你的答案里能主动说出“当数据量大时需要换一种思路”会比闷头写代码好很多。5.2 错题归因把每道错题归到知识点我整理这套 B 卷的时候做了一个简单的错题表把每道错题归到对应的知识点并标注错误原因是概念不熟、边界没考虑还是代码实现有问题。比如 KMP next 数组那道题我标的是“定义混淆”LIS 那道题我标的是“忘了考虑空数组”。这样做的好处是后续复习时不用重头再来只需要看错题表里高频出现的知识点就行。5.3 复盘模板题目、思路、复杂度、容易错点最后分享一个适合所有人的复盘模板。每做一道题不管对错都在笔记里按四栏记录题目简要描述、核心思路、复杂度、容易错点。小米这套 B 卷做完我的笔记大概长这样题目核心思路复杂度容易错点KMP next 数组最长相等真前后缀右移一位O(m)定义混淆快排双指针分区O(n log n)pivot 选第一个导致退化最长上升子序列dp[i] 表示以 i 结尾O(n²) / O(n log n)初始化遗漏区间调度按结束时间排序O(n log n)排序依据搞错这套模板用熟了之后你会发现很多题其实是在重复考同一个知识点。比如编辑距离、最长公共子序列、最长上升子序列本质上都是二维或一维 DP状态定义一换代码逻辑就很相似。把这些共同点提炼出来笔试的备考效率会提高很多。最后说个我自己的小习惯。每次笔试结束不管考得好不好我都会趁热把没写对的题重新归类写进同一个复盘文档并标上错误原因。小米这套 B 卷的 KMP 题我当时就写了四个字定义混淆。等下次再看到类似的 next 数组题我会先在草稿纸上把两种定义都列出来再动手。笔试本来就是个熟练活复盘到位了下一次才能真正避开同一个坑。