小米2020校招算法工程师笔试题一这份卷子在我带过的校招算法笔试里属于中规中矩但又很有代表性的类型。题量不算小选择题会卡时间编程题区分度明显整体风格非常贴近互联网大厂算法岗的通用考察套路——基础数据结构、排序和查找、字符串处理再加两到三道经典的算法编程题。如果你是准备投算法工程师岗位的应届生这套题里出现的很多知识点基本就是笔试前的复习大纲就算不是投小米拿去练手也完全合适。这篇文章我按复盘笔记的形式整理一下内容包含题目结构、考点分布、每一类题型的拆解思路以及我在实际带人准备过程中反复强调的失分点和复习方法。1. 题目总览这套卷到底在考什么1.1 题量、题型与时间分配感受先说整体结构。这套卷子大致是选择题加编程题两大部分。选择题大概在十几道到二十道之间每道题分值不高但覆盖的知识点非常杂从KMP的next数组、出栈序列合法性到排序稳定性、二分查找边界、复杂度递推式几乎把本科数据结构教材里的重点章节都扫了一遍。编程题三道难度明显是递进的第一道属于热身题第二道是中等搜索题第三道就是经典动态规划压轴。整场笔试的时间对我来说是偏紧的选择题如果纠结太久后面编程题基本写不完。这里有个很重要的经验这类传统大厂笔试选择题的设计初衷不是让你每道题都深入推导而是考察你知识面的宽度和熟练度。所以平时复习一定要把基础概念背到“条件反射”的程度比如看到快速排序立刻想到平均时间复杂度O(nlogn)、最坏O(n^2)、不稳定看到二分查找立刻想到区间开闭的写法。这些点说起来简单但考场上时间一紧最容易翻车的恰恰是这些“送分题”。1.2 高频考点盘点我把这套卷子涉及的知识点整理成了下面这张表方便你对照复习。这里的权重是按我个人对校招笔试出题习惯的判断给的不代表官方分数但方向基本不会偏。考察方向典型题目类型在卷子中的权重建议投入时间字符串算法KMP的next数组、字符串匹配中高一定要搞透栈和队列出栈序列合法性、单调栈中熟练模拟过程二叉树前序中序重建二叉树、遍历中高递归迭代双写排序算法稳定性、时间空间复杂度中高背熟对比表二分查找边界处理、旋转数组中固定一套模板复杂度分析递推式求复杂度中低主定理要会贪心算法区间调度、活动安排中掌握排序策略图论搜索BFS/DFS、岛屿问题中高必须手写熟练动态规划编辑距离、LIS高转移方程要推导清楚数学与位运算快速幂、取模中低模板代码背下来从这个表格能看出来这套卷子几乎没有偏题怪题全部是算法岗笔试的高频内容。它的筛选逻辑不是看你知不知道冷门算法而是看你在基础题上能不能拿满分编程题能不能稳定写出可运行的代码。1.3 出题人想筛选什么样的人我在准备校招那会儿导师跟我说过一句话笔试不是选拔天才是淘汰粗心的人。这套题很好地体现了这一点。选择题设置了很多“陷阱”比如KMP的next数组如果定义没看仔细很容易算出另一套结果排序稳定性的判断题很多人会栽在堆排序和选择排序上二分查找的边界写错一个符号就是死循环。所以出题人真正想考察的是你有没有工程落地的严谨性。代码题不给完整题目描述只给关键函数签名和输入输出要求你得自己处理边界条件自己考虑数据范围会不会溢出。这跟实际工作中写代码的状态是一样的——没有人会告诉你“这里要加个if”你得自己想到。2. 选择题拆解字符串、栈队列与二叉树2.1 那道让我印象深刻的KMP next数组题目这套题选择题里有一道关于KMP算法next数组的计算模式串是pabacaba要求写出next数组的取值。这道题我几乎每次给学弟学妹划重点都会提到因为它太经典了而且特别容易错。先说结论如果采用next[i]表示字符串p[0..i]的最长相等前后缀长度并且规定next[0]0那么逐项推导结果是i0子串是a没有真前后缀next[0]0i1子串ab前缀a后缀b不等next[1]0i2子串aba前缀a等于后缀a长度1next[2]1i3子串abac最长相等前后缀为0next[3]0i4子串abaca前缀a等于后缀a长度1next[4]1i5子串abacab前缀ab等于后缀ab长度2next[5]2i6子串abacaba前缀aba等于后缀aba长度3next[6]3所以这个定义下的next数组是[0,0,1,0,1,2,3]。但有一个特别容易踩的坑很多教材或模板把next数组定义为“失配时应该跳转到的下标”这时数组的值会整体错位比如变成[-1,0,0,1,0,1,2]。这两种写法算出来的结果不一样但都是“正确”的关键看你用的KMP实现是哪一种约定。做题之前一定要先看题目里给的定义是“最长相等前后缀长度”还是“失配跳转位置”否则后面全白算。对应到代码实现如果按第一种定义求next数组的标准写法长这样void buildNext(const string p, vectorint next) { int m p.size(); next.resize(m); next[0] 0; int j 0; // 当前已匹配的前后缀长度 for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; // 回退到更短的前缀 } if (p[i] p[j]) { j; } next[i] j; } }理解这段代码有个生活化类比你手里有一根绳子两端各有一段相同的花纹你不断把绳子两端往中间凑能重合多长就是next数组的值。一旦失配就往回收一段继续尝试。这个“回退”过程就是KMP比暴力匹配高效的核心能让文本串指针永不回头时间复杂度稳定在O(nm)。2.2 栈的后进先出出栈序列合法性判断另一道让我觉得很有代表性的选择题是出栈序列判断。题目会给你一个入栈序列比如1、2、3、4、5依次入栈然后问下面哪个出栈序列是合法的。这类题没有太多技巧核心就是用一个栈去模拟整个过程。举个例子判断序列3、1、2、4、5是否可能是出栈序列。我们从1开始模拟1入栈2入栈3入栈此时栈顶是3正好等于出栈序列的第一个元素3于是3弹出。接下来出栈序列要求弹1但当前栈顶是2栈底是12不弹的话1永远出不来。所以这个序列不合法。反过来3、2、1、5、4就是合法的因为3弹出后栈顶是2弹出再弹出1然后4入栈、5入栈、弹出5最后弹出4。这里有一个易错点不要试图用人脑倒推直接模拟反而是最快的。我见过不少同学在做这类题时喜欢凭感觉判断结果那种“看起来合理、模拟起来卡壳”的序列就很容易混过去。模拟时还要注意栈的容量限制有些题目会规定栈的最大深度虽然这套题里我没看到但你在牛客上刷题时大概率会遇到别忽略这个条件。2.3 二叉树前序中序重建二叉树二叉树相关的选择题在算法笔试里基本是必考的这套卷子也不例外。常考的一种形式是给出前序遍历和中序遍历要求你还原二叉树结构或者根据遍历序列判断树的形态。比如前序遍历序列是ABDCEF中序遍历序列是DBAECF。第一步前序遍历第一个元素A一定是根节点第二步在中序遍历里找到A左边DB是左子树的中序右边ECF是右子树的中序第三步回到前序BD是左子树的前序CEF是右子树的前序。递归处理左子树前序BD、中序DBB是根D是左孩子。右子树同理C是根EF分别是左右孩子。最终还原出来的树大概是这样的A / \ B C / / \ D E F这类题目想拿分核心是理解“前序找根、中序分左右”这个递归过程。建议你自己动手画一画把重建过程走两遍比看十遍解析都有用。另外一个高频变体是“后序中序”重建思路完全一样只是后序的最后一个元素是根节点。如果题目给的是前序后序反而无法唯一确定二叉树因为无法区分左右子树这个点也经常作为判断题出现。3. 排序、二分与复杂度基础但容易翻车3.1 排序算法稳定性与复杂度对照表排序算法是选择题的重灾区倒不是说题目难而是概念特别容易混淆。尤其是稳定性这个定义如果两个相等元素在排序前后的相对顺序保持不变就称这个排序算法是稳定的。注意这里的“相等元素”指的是关键字相同与它们在数组中的位置无关。我把常用的排序算法整理成一张表方便你直接背排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定冒泡排序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(nlogn)O(n^2)O(logn)~O(n)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定希尔排序与增量序列有关O(n^2)O(1)不稳定为什么快速排序不稳定因为它的分区操作会把元素跨越式地交换到很远的位置相等的元素完全可能被换到对方前面去。堆排序同理堆顶元素和堆尾元素交换时可能破坏相等元素的相对顺序。选择排序也是类似的问题一次选择会把后面的最小元素换到前面如果前面有相等元素顺序就乱了。而冒泡和插入每次只做相邻交换所以稳定。归并排序的稳定性来自合并时“左边优先”的处理策略写代码时注意是left[i] right[j]而不是否则会把相等元素顺序反过来。这套题里排序相关的选择题基本围绕这个表格展开比如问“下列哪些排序算法是稳定的”或者“要保证所有情况都是O(nlogn)应该选哪个”只要把上面这张表背熟这类题就是纯送分。3.2 二分查找边界写错就是死循环二分查找看起来简单但笔试里正确率一直不高。常见考法是给一个有序数组让你手写查找某个目标值的函数或者问在某个边界条件下循环会执行多少次。我记得这套题里有一道二分查找的变体不是直接找目标值而是找第一个大于等于目标值的位置相当于C里的lower_bound。我自己用的一直是“左闭右闭”模板因为它的边界条件最容易推理int lowerBound(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }这个模板的核心是当nums[mid] target时mid及其左边都不可能满足条件所以left mid 1否则mid可能是答案但右边更大所以保留mid把right mid - 1。循环结束后left指向第一个大于等于target的位置。这里有一个特别容易犯的错mid (left right) / 2在left和right都很大的时候会整数溢出应该写成left (right - left) / 2。虽然笔试不一定会因为这个扣分但面试官如果看到这行代码印象分会好很多。还有一个易错点while条件写left right还是left right直接影响后面的边界更新。如果写left right最后left会落在右边界右侧一格如果写left right则要注意避免死循环。我的建议是选定一套模板背熟不要再纠结两套写法的优劣考场上能稳定不bug的才是最好的。3.3 快速幂与复杂度递推这套题有一类让我印象比较深的选择题是给一个递推式让你求时间复杂度。比如T(n) 2T(n/2) O(n)对应的是归并排序结果是O(nlogn)T(n) T(n/2) O(1)对应二分查找结果是O(logn)。这类题用主定理Master Theorem可以直接解关键是能看出log_b(a)和f(n)的关系。校招笔试不会考太复杂的递推常见的就是a等于1或2、b等于2的几种情况记住结论即可。跟复杂度相关的还有一道快速幂的题比如求2^100 mod 7的结果。朴素做法是循环100次但快速幂能在O(logn)时间内算完原理是把指数拆成二进制100的二进制是1100100所以2^100 2^64 * 2^32 * 2^4每一项通过反复平方得到。模运算可以一步步取模防止中间结果溢出。这题如果手算甚至还能先发现规律2^122^242^38≡1(mod 7)所以2的幂次对7取模的周期是3100 mod 31答案就是2。不过考场上还是推荐直接用快速幂模板写代码来得快long long fastPow(long long base, long long exp, long long mod) { long long result 1; base % mod; while (exp 0) { if (exp 1) { result result * base % mod; } base base * base % mod; exp 1; } return result; }4. 编程题复盘贪心、搜索、动态规划一个不落4.1 第一题经典的区间调度问题编程题第一道通常不难但要求你快速写完并跑通。这套卷子的第一道编程题我印象里是区间调度类的问题给定若干区间选出尽量多的互不重叠区间返回最多能选多少个。学过贪心算法的同学应该秒懂——按区间结束时间排序然后依次选结束时间最早且与上一个选中区间不重叠的区间。为什么按结束时间排序而不是开始时间因为结束时间越早后面留给其他区间的空间就越大这是贪心算法能用在这个问题上的核心逻辑。按开始时间排序是典型的错误做法我见过太多人在这一步选错排序key导致答案全错。完整代码大概长这样struct Interval { int start; int end; }; int maxNonOverlapping(vectorInterval intervals) { if (intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; }); int count 0; int lastEnd INT_MIN; for (const auto iv : intervals) { if (iv.start lastEnd) { count; lastEnd iv.end; } } return count; }这里有个细节区间能不能相连要看题目定义。如果题目说[1,2]和[2,3]不算重叠那判断条件就写iv.start lastEnd如果边界相邻也算重叠就改成iv.start lastEnd。这个在笔试时一定要仔细读题不然后台用例会跑不过。另外区间可能没排序甚至可能有空区间输入数据的边界情况在刷题时要多注意。4.2 第二题网格搜索问题第二道编程题通常是图论搜索类这套卷子里比较有代表性的是“岛屿数量”问题。给定一个二维网格1表示陆地0表示水连通的陆地算一个岛屿问总共有几个岛屿。这是一道非常经典的BFS/DFS题理解了它很多网格搜索的变形题都能迎刃而解。核心思路是遍历整个网格遇到一个1就把岛屿计数加一然后从这个点出发把连在一起的所有1都标记成已访问。标记方式有两种一种是开一个visited布尔数组另一种是直接原地把访问过的1改成0。原地标记省空间笔试时也能省点代码量。我用DFS写过一版class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private: void dfs(vectorvectorchar grid, int i, int j) { if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] ! 1) { return; } grid[i][j] 0; dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } };这个写法最需要注意的一点是边界判断的顺序必须先判断下标是否越界再判断当前格子是不是1顺序反了会直接数组越界崩溃。另外如果网格特别大比如1000x1000递归DFS可能爆栈这时候可以改成BFS或者用显式栈模拟递归。BFS的写法就是在搜索时维护一个队列每弹出一个格子就把它四周满足条件的邻居入队。这题考察的是对搜索框架的熟练度代码本身不复杂关键是写的时候不要有遗漏分支。4.3 第三题动态规划之编辑距离压轴的动态规划题通常没有太多花哨的包装就是把经典的编辑距离问题搬上来。题目给定两个字符串word1和word2允许插入、删除、替换字符问把word1变成word2最少需要几步。我当时在笔试现场看到这题心里基本就有底了因为它是动态规划教科书级别的题目转移方程非常规整。用一个二维数组dp[i][j]表示word1的前i个字符变成word2的前j个字符所需的最少操作数。初始化部分dp[i][0] i表示把前i个字符全部删除dp[0][j] j表示把空串插入j个字符。转移的时候如果word1[i-1] word2[j-1]那这一步不需要操作直接继承dp[i-1][j-1]如果不相等就需要从三种操作中选最小的dp[i-1][j]代表删除word1的第i个字符dp[i][j-1]代表插入word2的第j个字符dp[i-1][j-1]代表替换当前字符。转移方程写出来就是dp[i][j] dp[i-1][j-1], 当 word1[i-1] word2[j-1] dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), 当 word1[i-1] ! word2[j-1]代码实现int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] 1 min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); } } } return dp[m][n]; }动态规划题最怕的不是转移方程不会写而是初始化出错。很多人会把dp[0][j]和dp[i][0]漏掉或者写反导致答案全部偏掉。我的建议是拿到题目后先在草稿纸上画一个(m1) x (n1)的表格把第一行第一列填好再手动模拟两三个格子确认状态定义没问题再写代码。笔试时间再紧张这一步也别省它相当于给自己做一次逻辑自检。编程题到这里基本覆盖了贪心、搜索、动态规划三大算法类型这也是校招算法笔试最常考的三大块。如果你有余力还可以再准备一下拓扑排序比如课程表问题和最短路径比如Dijkstra它们在稍难一点的场次会出现但核心思路跟上面的代码一样把框架写熟遇到变体往里套。5. 失分点统计与备考路线5.1 时间分配与做题顺序我见过太多同学在选择题上花太多时间最后一两道编程题只剩十分钟草草写几行伪代码就交卷。这个策略非常亏。我的建议是拿到卷子先花一两分钟把所有题目扫一遍把选择题里一眼会做的先做掉拿不准的标记一下放一放直接跳到编程题。编程题先做最容易拿分的第一题再做第二题最后有时间再挑战第三题。编程题每题的分值比单个选择题高得多一题能顶好几道选择题把编程题保住才是拿高分的关键。选择题如果卡了一道超过三分钟果断放弃。很多选择题是故意设计成“看起来复杂、其实简单”的比如KMP next数组只要一步步推就能写出来但你要是卡在某一行的推导上很可能被绕进去。这时候不如先猜一个答案标记好等做完编程题再回头检查。时间管理的核心就一句话把会做的题的分数完全拿到剩下的时间再拿来做难题。5.2 高频失分点速查表根据我带人复盘的经验这套卷子的错题高度集中在几个地方我整理成一张速查表考前最后几分钟过一遍非常有用。失分点原因对应的解决措施KMP next数组算错两种定义混淆先明确题目定义再推导出栈序列判断靠猜没有模拟栈过程所有题都手动模拟一遍稳定排序记反死记硬背结合交换方式理解记忆二分查找死循环while条件或mid取整不对固定使用左闭右闭模板区间调度排序key用错按开始时间排序记住按结束时间排序DFS边界判断顺序错先访问数组后判越界先判越界再判值DP初始化漏掉第一行列没有画表画表格再写代码快速幂中间结果溢出忘取模或乘数过大base先取模每次乘法取模5.3 针对这套卷的复习路线最后聊一下如果要从头准备该怎么规划。复习路线不用太复杂核心围绕“字符串、排序、搜索、动态规划”四个方向展开。字符串方向重点练KMP其次是简单模式匹配排序方向要求能手写冒泡、快排、归并并能说出稳定性搜索方向把DFS和BFS的经典题刷个20道包括岛屿数量、走迷宫、二叉树遍历动态规划方向先把编辑距离、最长上升子序列、01背包三道题吃透再扩展其他题型。刷题数量固然重要但刷题后的复盘更重要。我建议每做完一道题问自己三个问题这题的核心思路是什么我第一遍做的时候卡在哪一步如果考场上遇到类似题我能不能快速写出框架把这三点写在笔记里比闷头刷一百道题有效得多。尤其是KMP和区间调度这种“思路清晰但细节多”的题笔记能帮你快速回顾而不是重新推导一遍。带人复盘这套题的时候我还有个感受能走到面试的同学往往不是把最后一道难题写出来的那种而是简单题不丢分、编程题第一问拿满分、第二问有思路能写出来的那种。笔试考的是稳定输出不是灵光一闪。所以我的建议是考前把KMP、快排、区间调度、BFS、编辑距离这五类题反复写到能默写的程度考场上先把送分题做对再啃硬骨头。把这件事做好比刷十套难题都管用。