企业官网建设流程全解析

小米2020校招算法工程师笔试题二，这套卷子在当年的校招圈里流传度相当高。不是说它难到离谱，而是它的考察点特别“正”：字符串处理、排序选型、动态规划、贪心、树结构，几乎把算法岗笔试最常见的题型都串了一遍。我身边不少同学在刷完这套题之后，对后续其他厂的笔试都有了底气。这篇文章把整张卷子按考点拆成六个模块，结合我自己刷题时的思路和踩坑记录，把每题的手算过程、完整代码和易错点都过一遍。不管你是正在备战校招的应届生，还是想系统梳理算法基础的从业者，这套题都值得认真做一遍。

1. 小米2020校招算法工程师笔试题二：整体结构与考点拆解

1.1 这套卷子的命题风格与难度定位

小米算法岗的笔试风格延续了很多年，核心就一句话：基础不基础，一测便知。它不会故意出偏题怪题，但会把经典题目包装成比较贴近工程实际的场景，比如给你一堆学生记录让你选排序算法，或者给你一段模式串让你手算KMP的next数组。这种题目看起来不起眼，实际上筛人非常狠，因为背过答案的人和不理解原理的人，在写推导过程时一眼就能分辨出来。

从难度定位上看，这套试卷的整体难度在互联网大厂校招中属于中等偏上。字节的算法题偏重代码量和边界测试，美团的题偏重业务场景和工程设计，而小米的题更像是“教科书上的经典题换了一层皮”。它更适合那些把《数据结构与算法》基础打得比较扎实的候选人。如果你只是刷过两三百道LeetCode但没系统梳理过原理，做这套卷子会明显感觉到基础概念的薄弱。

另一个值得注意的点是，这套卷子的题型灵活性比较高，同一道题可以考选择题，也可以考简答题，甚至拆成多个小问。比如KMP那道题，既可以只让你填next数组，也可以让你写出失配时模式串的移动位置。所以我强烈建议在刷题时不要只盯着一问，把每一道经典题的周边知识点都捋一遍。

1.2 核心算法模块与准备优先级

根据这套卷子覆盖的内容，我把算法岗笔试最高频的考察模块整理成了下面这张表。准备笔试时，按照表格里的优先级顺序安排时间，效率会高很多。

我在实际刷题时发现，很多同学容易在低优先级的模块上死磕，反而忽略了排序和字符串这两个最基础的大头。其实算法岗笔试的及格线，往往就是由这些基础模块决定的。智能优化算法这类题，小米偶尔会考一个概念或者思想来源，比如粒子群算法是模拟鸟群觅食，模拟退火算法是模拟金属退火过程，知道核心思路就能做对，完全没必要在这上面花大量时间。

2. KMP算法真题：next数组手算与失配跳转

2.1 题目回顾与next数组的推导过程

这套卷子里有一道很典型的KMP题，题目描述大概是这样的：在KMP算法中，对于模式串 P = "abacaba"，其 next 数组定义为 next[i] 表示 P[0..i-1] 的最长相等前后缀长度，约定 next[0] = -1，请计算模式串 P 的 next 数组，并回答当匹配到第 6 个字符失配时，模式串应该向右移动几个字符。

我先把手算过程完整写出来。模式串 P = "abacaba"，一共 7 个字符，下标从 0 开始。next[0] 按约定为 -1。next[1] 表示 P[0..0] 即 "a" 的最长相等前后缀长度，长度不够 2 时统一记为 0，所以 next[1] = 0。接下来逐项推导：

• next[2]：前缀为 "ab"，前缀集合是 {"a"}，后缀集合是 {"b"}，没有交集，长度为 0。
• next[3]：前缀为 "aba"，前缀有 {"a", "ab"}，后缀有 {"ba", "a"}，公共部分是 "a"，长度为 1。
• next[4]：前缀为 "abac"，前缀集合 {"a", "ab", "aba"}，后缀集合 {"bac", "ac", "c"}，交集为空，长度为 0。
• next[5]：前缀为 "abaca"，前缀集合里最长到 "abac"，后缀集合里最长到 "aca"，交集只有 "a"，长度为 1。
• next[6]：前缀为 "abacab"，前缀集合最长到 "abaca"，后缀集合最长到 "bacab"，交集是 "ab"，长度为 2。
• next[7]：前缀为 "abacaba"，前缀集合最长到 "abacab"，后缀集合最长到 "bacaba"，交集是 "aba"，长度为 3。

所以完整的 next 数组为 [-1, 0, 0, 1, 0, 1, 2, 3] 和模式串长度对应 8 个元素。很多同学会问，模式串一共 7 个字符，为什么 next 数组有 8 个元素？因为 next[i] 在定义上对应的是第 i-1 个字符之前的那段前缀，失配位置可以从 0 到 7，所以数组长度是 m+1。这个细节笔试时最容易丢分。

2.2 KMP完整实现与失配移动位置计算

题目第二问问的是第 6 个字符失配时模式串移动多少位。注意这里的“第 6 个字符”对应下标 5，也就是 b 这个位置。查询 next[5] = 1，说明失配后 j 指针要回退到下标 1 的位置继续匹配，也就是模式串从原先指向下标 5 的位置变成指向下标 1，整体向右移动 j - next[j] = 5 - 1 = 4 位。

我给出一个可以直接跑的KMP实现，注释里标注了关键逻辑：

def get_next(p: str): m = len(p) nxt = [-1] * (m + 1) i, j = 0, -1 while i < m: if j == -1 or p[i] == p[j]: i += 1 j += 1 nxt[i] = j else: j = nxt[j] return nxt def kmp_search(t: str, p: str): n, m = len(t), len(p) nxt = get_next(p) i = j = 0 positions = [] while i < n: if j == -1 or t[i] == p[j]: i += 1 j += 1 else: j = nxt[j] if j == m: positions.append(i - j) j = nxt[j] return positions, nxt t = "abacababacaba" p = "abacaba" positions, nxt = kmp_search(t, p) print("next数组:", nxt) print("匹配位置:", positions)

这里有一点必须提醒：KMP 的时间复杂度是 O(n+m)，原理在于 j 指针虽然会回退，但 i 指针始终不回头。匹配过程中文本串的每个字符最多被比较一次，而 j 回退的总次数不会超过 j 前进的总次数，所以整体是线性复杂度。很多人背下了模板却说不清为什么线性，面试追问时很容易露馅。

2.3 nextval优化与不同定义的坑

关于KMP，笔试里还有一个高频衍生考点：nextval 数组。nextval 的作用是当回退后的字符和当前失配字符相同时，继续回退就没有意义，可以直接把 nextval 指向更深层的跳转位置，省掉一次无意义的字符比较。

计算规则不复杂：如果 p[i] == p[next[i]]，那么 nextval[i] = nextval[next[i]]，否则 nextval[i] = next[i]。对模式串 "abacaba" 来说，每一步回退到的字符都和当前字符不同，所以 nextval 数组和 next 数组完全一样。这也是很多教材选这个例子做讲解的原因，它不会产生干扰项。

真正需要警惕的是 next 数组定义不统一的问题。有些教材把 next[i] 定义为模式串下标 i 处失配时应该跳转到的下标，而不是“前 i 个字符的最长相等前后缀长度”，这两种定义算出来的数值在表示上完全不一样。我在刷题时见过同学在牛客评论区因为答案不一致吵起来，实际上两个答案在自己的定义下都是对的。考试时务必先看清题目给出的定义再下笔。

3. 排序算法真题：稳定性、快排退化与场景选型

3.1 场景题：按总分和姓名排序应该选什么算法

这套卷子里的排序题考得很实在，题目是这样的：假设有一批学生记录，需要先按总成绩降序排列，总成绩相同的按姓名字典序升序排列，要求排序结果必须稳定，你会选择哪种排序算法并说明理由。

这是一道典型的“场景选型”题，考察点有两个：第一，你知不知道哪些排序算法稳定；第二，你能不能把稳定性概念应用到多关键字排序里。答案是归并排序，因为归并在时间复杂度为 O(n log n) 的算法里是天然稳定的。如果选择快速排序，虽然平均时间也是 O(n log n)，但它是不稳定的，两个相同成绩的学生可能在排序后交换先后顺序，导致第二关键字的排序失效。

这里有一个实用小技巧：如果数据量很小，比如不到几十条记录，直接选择插入排序也是完全可行的，因为插入排序稳定且常数极小。在实际工程里，标准库的排序往往会在递归到小区间时切换到插入排序，比如 Python 的 TimSort 底层就融合了归并排序和插入排序，兼顾稳定性与性能。笔试时如果能把这个点写出来，会是一个明显的加分项。

我整理了一张排序算法核心参数对比表，笔试前建议反复默写：

3.2 快速排序退化问题与优化策略

快速排序是笔试常客，但这套卷子没有简单地问“快排的思想是什么”，而是问了一个很实际的问题：当输入数组已经是有序的，快速排序为什么会退化到 O(n^2)，有什么优化手段。

退化原因很简单：如果每次选择的基准都是当前区间的最小值或最大值，那么每次划分只能把区间分成 1 和 n-1 两部分，递归深度变成 n，总比较次数变成 O(n^2)。经典快排的基准是固定取第一个元素，有序输入恰好命中退化场景。

优化手段有几个层次。第一层是随机化，即随机选取基准元素，把退化概率降到极低；第二层是三数取中，从区间左端、中间、右端三个位置取中位数做基准，对抗部分恶意构造的输入；第三层是三路快排，把等于基准的元素单独放中间区域，对于大量重复元素的数组来说，三路快排能避免重复元素反复参与比较。

更进一步的工程级优化，是在递归区间长度小于某个阈值时改用插入排序。这个思路在很多开源库的排序实现里都有体现。笔试如果考到快排优化，建议从“基准选择、重复元素处理、小区间切换”三个方向组织答案，覆盖足够全面。我个人的实操经验是，手写快排时哪怕只加一个随机基准，就能让算法在各种刁钻输入下稳定很多。

4. 动态规划真题：LIS与0-1背包的破题思路

4.1 最长上升子序列的两种解法和复杂度对比

这套卷子的动态规划编程题出了一道最长上升子序列问题，给了一组数 [10, 9, 2, 5, 3, 7, 101, 18]，要求计算最长的严格上升子序列长度。这道题虽然经典，但能区分出考生到底理解 DP 还是只会背模板。

先看最基本的 O(n^2) 解法。定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列长度，初始时每个元素单独成序列，dp[i] = 1。对于每一个 i，遍历所有 j < i，如果 nums[j] < nums[i]，说明可以接在后面，dp[i] = max(dp[i], dp[j] + 1)。按这个逻辑计算整组数据，最后的答案是 4，对应子序列 [2, 3, 7, 101] 或 [2, 3, 7, 18]。

如果笔试要求优化，就需要拿出贪心加二分的 O(n log n) 解法。核心思路是维护一个数组 tails，tails[k] 表示长度为 k+1 的上升子序列中末尾元素的最小值。遍历 nums 的每个元素 x，在 tails 中找到第一个大于等于 x 的位置，把该位置更新为 x；如果 x 比 tails 所有元素都大，就追加到末尾。这样遍历完后 tails 的长度就是答案。

我用例子推一遍 tails 的变化：初始空数组，遇到 10 追加为 [10]，遇到 9 替换为 [9]，遇到 2 替换为 [2]，遇到 5 追加为 [2,5]，遇到 3 替换为 [2,3]，遇到 7 追加为 [2,3,7]，遇到 101 追加为 [2,3,7,101]，遇到 18 替换为 [2,3,7,18]。最终长度是 4。

虽然 tails 里存的并不一定是真实的最长上升子序列，但长度一定是正确的最长上升子序列长度。这个性质刚接触时容易想不通，我最初也卡了很久。理解的关键在于：tails 数组中每个位置维护的是“当前长度下尽可能小的末尾元素”，末尾越小，后面越容易接上更大的数，这样就把问题转化成了一个不断更新最小末尾的贪心过程。

4.2 0-1背包变体：滚动数组为什么必须逆序更新

编程题第二道动态规划是典型的 0-1 背包问题变体：有 N 件物品和一个容量为 V 的背包，第 i 件物品的重量是 weight[i]，价值是 value[i]，每件物品最多只能取一次，求背包能装下的最大总价值。

最直接的二维状态定义是 dp[i][j] 表示前 i 件物品装入容量为 j 的背包能获得的最大价值。状态转移时，对于第 i 件物品有两种选择：不装，则 dp[i][j] = dp[i-1][j]；装，则 dp[i][j] = dp[i-1][j-weight[i]] + value[i]，前提是 j >= weight[i]。两者取最大值。

笔试时间紧张时，我会直接写滚动数组版本，因为代码更短。一维数组 dp[j] 滚动更新，转移公式是 dp[j] = max(dp[j], dp[j-weight[i]] + value[i])。关键点在于内层循环必须从 V 向下遍历到 weight[i]，也就是逆序更新。

为什么一定要逆序？因为一维数组滚动更新时，如果正序，dp[j-weight[i]] 可能在当前物品的同一轮更新中已经被覆盖，这时候再拿来计算就相当于这个物品被放了多次，变成了完全背包问题。逆序可以保证 dp[j-weight[i]] 仍然来自上一轮状态，也就是前 i-1 件物品的最优解。

我提供一个简短的实现：

def knapsack_01(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity] weights = [2, 3, 4, 5] values = [3, 4, 5, 6] print(knapsack_01(weights, values, 8))

这个例子的最优结果是装入重量为 3 和 5 的两件物品，总重量 8，总价值 10。笔试时如果遇到背包类问题，建议先把题目里“每个物品取几次”这个条件读清楚，0-1背包逆序更新，完全背包正序更新，这个区别几乎每年都在考。

5. 贪心与树结构真题：区间调度与最近公共祖先

5.1 区间调度问题：为什么按结束时间排序是对的

这套卷子里的贪心题考察的是活动选择问题，也叫区间调度问题。题目给出若干个活动区间，每个活动有一个开始时间 start 和一个结束时间 end，要求选出尽可能多的互不重叠的活动。我印象里题目给的数据是 [[1, 3], [2, 4], [3, 6], [5, 7], [6, 8]]。

这道题的正确策略是按结束时间从小到大排序，然后依次选择：只要当前活动的开始时间不早于上一个选中活动的结束时间，就把它选进来。按结束时间排序后，区间变成 [1,3], [2,4], [3,6], [5,7], [6,8]。选择 [1,3] 后，[2,4] 的开始时间 2 小于上一个结束时间 3，跳过；[3,6] 可以选；然后 [5,7] 的开始时间 5 小于 6，跳过；[6,8] 可以选。最终选中的是 [1,3], [3,6], [6,8]，一共 3 个。

为什么按结束时间排序就一定能得到全局最优？这才是大佬和普通人的区别。核心论证思路是：对于任意一个最优解，如果它的第一个活动不是所有活动中结束时间最早的那个，那么可以用结束时间最早的活动替换它，替换后剩余可用的时间只会更多或不变，原最优解后面的活动仍然可以全部保留。以此类推，每一步都做结束时间最早的贪心选择，和某个全局最优解最多只差一次替换，所以贪心解就是全局最优解。

笔试答贪心题时，光写“这是个贪心问题”拿不到满分，至少要把交换论证的几步讲清楚。这道题其实是典型的“证明简单，想到难”的题目，提前把证明思路背熟，考场上有备无患。

5.2 二叉树的最近公共祖先：递归与迭代两种实现

树结构在笔试题里通常是编程题压轴，这套卷子考的是二叉树的最近公共祖先问题。给定一棵二叉树和两个节点 p、q，找到它们的最近公共祖先。注意这里不是二叉搜索树，不能直接用节点值比较来决定向左还是向右，必须老老实实递归遍历。

递归解法的核心思路是：从根节点开始，如果当前节点为空或者等于 p 或 q，直接返回当前节点；否则分别在左子树和右子树中查找。如果左右子树的返回值都不为空，说明 p 和 q 分别位于当前节点的左子树和右子树中，当前节点就是最近公共祖先。如果只有一侧返回值非空，就返回那一侧的结果。

我给出递归实现：

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right

这个解法的边界情况比较隐蔽，我刷题时踩过几个坑。第一个坑是 p 和 q 中有一个节点是另一个节点的祖先，这时递归到祖先节点会直接返回，不会再往下找，结果恰好正确。第二个坑是 p 或 q 可能不在树里，题目如果保证存在就忽略，如果没保证需要额外记录查找结果。第三个坑是递归深度，极端情况下树退化成链表，递归可能爆栈，工程上可以用迭代法通过哈希表记录父节点来规避。

迭代法的思路是：用层序遍历或栈遍历整棵树，同时用一个字典 parent 记录每个节点的父节点。遍历完所有节点后，从 p 开始不断向上跳到根，把经过的所有节点存入一个集合；再从 q 开始向上跳，遇到第一个已经在集合里的节点就是最近公共祖先。这个写法牺牲了一点空间，但逻辑非常直观，适合在面试讲解时用。

6. 笔试现场复盘：易错点与训练建议

6.1 考场中最容易犯的10个错误

我复盘了这套卷子以及同期其他同学的反馈，整理出十个最容易丢分的点。这些坑很基础，但每年都有人反复踩。

这里重点说说第 10 条。很多人觉得笔试只看代码能不能过，推导过程不重要，实际上像小米这类公司，笔试题后面往往跟着面试复盘，面试官真的会看你在试卷上留下的推导痕迹。KMP 那道题哪怕 next 数组算错了，只要你把推导过程写清楚，面试官很容易判断你是计算失误还是概念不清，这两者的评价完全不同。

6.2 刷题训练顺序与时间分配建议

如果你是把这套卷子当作模拟训练，我建议按“基础巩固、专题突破、整套模拟”三个阶段来安排时间。基础巩固阶段先把排序和字符串这两块吃透，尤其是 KMP 的 next 数组手算，至少亲手推 10 个不同模式的串；专题突破阶段集中刷动态规划和贪心，背包、LIS、区间调度这三类题目务必做到无脑写模板的速度；整套模拟阶段严格按照笔试时间限制来训练，留出至少 20 分钟检查。

时间分配上，我个人觉得动态规划和树结构应该占掉 40% 的训练时间，因为这两个模块在笔试中的权重最高，而且代码量也最大。排序和字符串占到 30%，剩下的分给贪心、二分和数学基础。智能优化算法这类偏概念的内容，考前用半天过一遍核心思想就够了，比如粒子群算法的速度位置更新公式、模拟退火算法的温度衰减逻辑，知道大概场景就能应付选择题。

最后再分享一个考场上的小习惯：遇到编程题，先花 30 秒把状态定义写在草稿纸上，再写转移方程，最后写代码。这个习惯能很大程度减少动态规划题目里的“思路是对的但状态定义和转移对不上”的尴尬情况。我自己在刷这套卷子时，LIS 和背包那两道题都是先写状态定义再撸代码，基本一次通过。