小米2020校招算法工程师笔试题二这套卷子在当年的校招圈里流传度相当高。不是说它难到离谱而是它的考察点特别“正”字符串处理、排序选型、动态规划、贪心、树结构几乎把算法岗笔试最常见的题型都串了一遍。我身边不少同学在刷完这套题之后对后续其他厂的笔试都有了底气。这篇文章把整张卷子按考点拆成六个模块结合我自己刷题时的思路和踩坑记录把每题的手算过程、完整代码和易错点都过一遍。不管你是正在备战校招的应届生还是想系统梳理算法基础的从业者这套题都值得认真做一遍。1. 小米2020校招算法工程师笔试题二整体结构与考点拆解1.1 这套卷子的命题风格与难度定位小米算法岗的笔试风格延续了很多年核心就一句话基础不基础一测便知。它不会故意出偏题怪题但会把经典题目包装成比较贴近工程实际的场景比如给你一堆学生记录让你选排序算法或者给你一段模式串让你手算KMP的next数组。这种题目看起来不起眼实际上筛人非常狠因为背过答案的人和不理解原理的人在写推导过程时一眼就能分辨出来。从难度定位上看这套试卷的整体难度在互联网大厂校招中属于中等偏上。字节的算法题偏重代码量和边界测试美团的题偏重业务场景和工程设计而小米的题更像是“教科书上的经典题换了一层皮”。它更适合那些把《数据结构与算法》基础打得比较扎实的候选人。如果你只是刷过两三百道LeetCode但没系统梳理过原理做这套卷子会明显感觉到基础概念的薄弱。另一个值得注意的点是这套卷子的题型灵活性比较高同一道题可以考选择题也可以考简答题甚至拆成多个小问。比如KMP那道题既可以只让你填next数组也可以让你写出失配时模式串的移动位置。所以我强烈建议在刷题时不要只盯着一问把每一道经典题的周边知识点都捋一遍。1.2 核心算法模块与准备优先级根据这套卷子覆盖的内容我把算法岗笔试最高频的考察模块整理成了下面这张表。准备笔试时按照表格里的优先级顺序安排时间效率会高很多。考察模块代表考点常见出现形式准备优先级字符串算法KMP、next数组、字符串哈希选择/填空/简答极高排序算法稳定性、复杂度对比、快排退化选择/简答极高动态规划LIS、0-1背包、状态压缩编程题极高贪心算法区间调度、活动选择、最优装载简答/编程高树结构二叉树遍历、最近公共祖先编程/简答高二分查找左右边界、浮点二分选择/编程中高数学基础快速幂、最大公约数、素数筛选择/填空中智能优化算法粒子群、模拟退火的基本思想选择/概念中低我在实际刷题时发现很多同学容易在低优先级的模块上死磕反而忽略了排序和字符串这两个最基础的大头。其实算法岗笔试的及格线往往就是由这些基础模块决定的。智能优化算法这类题小米偶尔会考一个概念或者思想来源比如粒子群算法是模拟鸟群觅食模拟退火算法是模拟金属退火过程知道核心思路就能做对完全没必要在这上面花大量时间。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所以数组长度是 m1。这个细节笔试时最容易丢分。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(nm)原理在于 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 底层就融合了归并排序和插入排序兼顾稳定性与性能。笔试时如果能把这个点写出来会是一个明显的加分项。我整理了一张排序算法核心参数对比表笔试前建议反复默写排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定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) 解法。核心思路是维护一个数组 tailstails[k] 表示长度为 k1 的上升子序列中末尾元素的最小值。遍历 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个错误我复盘了这套卷子以及同期其他同学的反馈整理出十个最容易丢分的点。这些坑很基础但每年都有人反复踩。序号错误类型具体表现规避方法1next数组定义不清不知道 next[0] 取 -1 还是 0先确认题目定义再计算2忽略排序稳定性多关键字排序选了快排背诵稳定性表格3快排退化场景判断错误认为有序输入效率最高记住有序对快排最不友好4背包遍历方向写反0-1背包写成正序更新逆序更新逐轮推状态5LIS的dp初始值错误初始值从0开始每个元素自己算长度16区间调度排序依据错误按开始时间排序按结束时间排序并证明7递归边界遗漏空节点p或q为空时未处理统一判空8二叉树祖先链判断错误忽略 p 是 q 祖先的情况用集合存储完整祖先链9时间复杂度分析缺失写完代码不说明复杂度每个算法补一句复杂度10手算过程不写只给答案不给推导步骤分比结果分更稳这里重点说说第 10 条。很多人觉得笔试只看代码能不能过推导过程不重要实际上像小米这类公司笔试题后面往往跟着面试复盘面试官真的会看你在试卷上留下的推导痕迹。KMP 那道题哪怕 next 数组算错了只要你把推导过程写清楚面试官很容易判断你是计算失误还是概念不清这两者的评价完全不同。6.2 刷题训练顺序与时间分配建议如果你是把这套卷子当作模拟训练我建议按“基础巩固、专题突破、整套模拟”三个阶段来安排时间。基础巩固阶段先把排序和字符串这两块吃透尤其是 KMP 的 next 数组手算至少亲手推 10 个不同模式的串专题突破阶段集中刷动态规划和贪心背包、LIS、区间调度这三类题目务必做到无脑写模板的速度整套模拟阶段严格按照笔试时间限制来训练留出至少 20 分钟检查。时间分配上我个人觉得动态规划和树结构应该占掉 40% 的训练时间因为这两个模块在笔试中的权重最高而且代码量也最大。排序和字符串占到 30%剩下的分给贪心、二分和数学基础。智能优化算法这类偏概念的内容考前用半天过一遍核心思想就够了比如粒子群算法的速度位置更新公式、模拟退火算法的温度衰减逻辑知道大概场景就能应付选择题。最后再分享一个考场上的小习惯遇到编程题先花 30 秒把状态定义写在草稿纸上再写转移方程最后写代码。这个习惯能很大程度减少动态规划题目里的“思路是对的但状态定义和转移对不上”的尴尬情况。我自己在刷这套卷子时LIS 和背包那两道题都是先写状态定义再撸代码基本一次通过。