2026/8/30 19:55:28
FEATURED · 精选文章 
作为一名参加过2022年秋招、被小米算法卷实打实虐过一遍的过来人看到这个标题我DNA都动了。这份卷子在当时算得上是几家大厂里风格比较鲜明的一套它不纯粹考刷题量而是很看重基础算法原理的深度和代码实现的严谨度。哪怕放到现在里面涉及的考点依然是面试和笔试的高频核心像KMP的next数组、堆排序的手写、贪心和动态规划的辨析几乎每家大厂笔试都会换着法子考。这篇文章我就把这份卷子的整体结构、核心题目拆解、代码实现以及我踩过的坑完整复盘一遍希望能帮准备算法岗笔试的朋友少走弯路。1. 笔试整体拆解与考点分析1.1 题型构成与考察形式2022年小米秋招算法岗笔试的卷2整体题量属于中等偏上我记得好像是单选、多选混合的选择题大概20道左右加上两道编程大题总时长在90分钟到120分钟之间。这个体量设计得很刁钻它不指望你把所有题都写完而是通过这种题量分布来区分「刷题机器」和「真正理解算法本质的人」。选择题的考察范围非常广从数据结构、排序算法、图论、动态规划到机器学习基础都有涉及。这跟纯刷LeetCode的考核方式完全不同它更偏向于考察你对算法原理的「理解深度」而非「调用能力」。比如它不会直接让你写一个排序而是问你快速排序在某种特定输入下的最坏时间复杂度是多少或者堆排序的建堆过程具体发生了多少次比较。编程题部分则回归了传统笔试风格两道题都属于“看一眼知道考什么但动手写就容易翻车”的类型。一道是字符串处理相关的KMP变种题另一道是结合了贪心思想的数组操作题。这两道题我没有当场AC完整第二题只过了部分测试用例后来复盘才发现是边界条件漏判了这部分我会在后面章节详细展开。1.2 核心考点分布与难度评估我把这套卷子涉及的核心考点按出现频次和难度整理成了一个表格方便大家直观感受备考优先级考点类别具体知识点出现频次难度评估字符串匹配KMP算法、next数组计算高中等排序算法快排、堆排、归并的复杂度与稳定性高低-中等动态规划经典DP模型、状态转移推导高中高贪心算法经典贪心场景辨析中中等图论算法最短路径、最小生成树中中等机器学习SVM、决策树、聚类基础概念低低数学基础快速幂、位运算中低从这个分布也能看出小米的算法笔试风格其实很像“考研408 LeetCode热题100”的混合体。数据结构基础扎实的同学会占很大优势而那些只刷题不看书的人反而容易在选择题上翻车。另外我注意到一个细节卷子里出现了KL散度相关的选择题虽然热搜词里很多人搜的是“KL ELBO算法原理详解”但笔试实际考察的并不深只是问KL散度是否为对称度量以及它在变分推断里的基本作用。这说明它不是想考你推导而是看你了不了解这个概念本身。提示如果你准备时间有限重心一定要放在字符串匹配、排序、DP和贪心上机器学习相关概念只要把常见模型的优缺点背熟即可不会出太偏的题。2. 高频算法题逐一拆解与答题思路2.1 KMP算法的next数组计算与失配指针原理这份卷子的选择题里有一道很经典的题给定模式串“abacaba”要求计算它的next数组。这个字符串我印象太深了因为它在KMP学习里属于非常具有代表性的例子包含了前缀后缀的嵌套关系。先回忆一下next数组的定义next[i]表示模式串前i个字符组成的子串中最长相等前缀后缀的长度通常不包含自身即长度小于i。计算“abacaba”的next数组过程是这样的i1时子串“a”没有真前缀和真后缀next[1]0i2时子串“ab”前缀“a”和后缀“b”不匹配next[2]0i3时子串“aba”前缀“a”与后缀“a”匹配长度为1next[3]1i4时子串“abac”最长相等前缀后缀为0next[4]0i5时子串“abaca”前缀“a”和后缀“a”匹配长度为1next[5]1i6时子串“abacab”前缀“ab”和后缀“ab”匹配长度为2next[6]2i7时子串“abacaba”前缀“aba”和后缀“aba”匹配长度为3next[7]3。所以最终next数组是[0, 0, 1, 0, 1, 2, 3]。这道题如果理解透彻了30秒内就能算完。但如果你只是记住了代码模板而不理解原理遇到这种稍微变形一点的问题就容易懵。KMP的核心思想就是利用已经匹配的部分信息让模式串在失配时可以向右滑动尽可能远的距离。next数组保存的正是这个“滑动距离”的依据。面试时如果被追问还会让你解释为什么next数组能保证不漏匹配这就涉及到了失配时的“安全位移”概念。笔试虽然不考推导但考计算能力所以一定要多手动推导几个字符串的next数组练出手感。2.2 排序算法复杂度、稳定性与适用场景对比排序算法在小米这套卷子里占比不低而且考察方式非常灵活。选择题里直接考了堆排序建堆的比较次数、快速排序在已经有序数组上的表现、归并排序的空间复杂度等。关于堆排序有一个容易错的知识点建堆的时间复杂度不是一个一个插入的O(n log n)而是O(n)。原因是自底向上的下滤操作大部分节点都不会下沉太深。选择题里如果问建堆复杂度一定要选O(n)而不是O(n log n)。快速排序的退化场景也是一大考点。当输入数组已经有序或者逆序时如果每次选的基准都是首元素或尾元素那分区极度不平衡递归深度变成n时间复杂度退化到O(n²)。这也是为什么实际工程中会用随机化快排或三数取中法来避免这个情况。关于稳定性我在备考时专门做了个总结表笔试选择题直接套用就行排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)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²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定这套表看似简单但真正的考点在于组合比如“统计一个数组中有多少逆序对用什么排序思想可以在O(n log n)内解决”答案是归并排序再比如“如果数组基本有序选择哪个排序算法效率最高”答案是插入排序因为它的最好情况是O(n)。这些都是小米选择题的常见变形。2.3 动态规划与贪心策略的典型题目辨析动态规划和贪心是算法笔试中的“重头戏”这套卷子的选择题里出现了好几道编程题里也有一道。它们之间的核心区别在于贪心算法每一步做局部最优选择期望能达到全局最优动态规划则通过穷举所有子问题并记录最优结果来保证全局最优。选择题里有一道非常经典的辨析题给定一组区间问如何选择最多数量的互不重叠区间。这道题的正解是贪心——按照区间结束时间排序每次选择结束最早且与前面不冲突的区间。但如果把题目改成“选择区间使得覆盖总长度最大”贪心就不成立了需要动态规划。小米这类题考得就是这个“能否识别出贪心不适用场景”的能力。我还记得编程题第二道就是类似“跳跃游戏II”的变种给定一个非负整数数组每个元素代表从当前位置最多能跳多远问最少跳几次能跳到最后一个位置。这道题贪心可以解需要维护当前跳跃能达到的边界和下一步能达到的最远位置。核心思路是在当前步的覆盖范围内遍历不断更新下一步能达到的最远位置当遍历到当前边界时步数加一。边界条件是数组长度为1时返回0这个条件我当时漏了导致部分用例不过。2.4 图论算法最短路径与最小生成树的考点图论这部分小米卷2考了一道关于Dijkstra算法的选择题问的是在什么情况下Dijkstra算法会失效。正确答案是当图中存在负权边时Dijkstra基于贪心策略的假设会被打破。这个知识点几乎每家公司的算法笔试都会考因为很多人只背了代码却没想过为什么它不能处理负权边。另外还考了最小生成树具体题目是问Kruskal算法和Prim算法的适用场景区别。Kruskal按边权重从小到大排序适合稀疏图边数远小于顶点数平方的图Prim按点逐步扩张适合稠密图。这个区分点很关键我把它记成了“Kruskal管边Prim管点”。如果你能把这两个算法各自的优化方式也搞明白——比如Prim可以用优先队列优化Kruskal依赖并查集——那选择题基本就不会失分了。还有一道题涉及Kahn算法即拓扑排序的BFS实现方法。考察的是入度为零的节点依次入队的过程以及当图中有环时队列会提前为空的现象。这道题的变形做法是通过Kahn算法统计出队节点数量如果小于总节点数则说明图中存在环。2.5 机器学习基础SVM、决策树与聚类的浅层考察小米算法笔试卷里居然混进了几道机器学习相关的选择题这一点当时让不少只刷算法题的同学措手不及。虽然题目难度不大但如果你完全没接触过就只能靠蒙。有一道题是问SVM的核函数中哪个参数控制模型复杂度。答案是gamma。gamma越小高斯核函数的作用范围越大决策边界越平滑gamma越大每个训练样本的影响范围越小越容易过拟合。这道题属于典型的面试概念题不需要推导公式但需要理解参数含义。还有一道关于决策树特征选择的题问的是信息增益在有多个取值特征的场景下容易偏向哪种特征。答案是取值多的特征。如果属性类别过多每个分支下的样本会很少纯度会异常地高因此信息增益会产生偏好。这种问题的正解通常是采用增益率来校正这也是C4.5算法的改进动机。聚类的题考的是K-Means的收敛行为问其目标函数是什么以及是否一定能收敛到全局最优。答案是它能保证收敛到局部最优但不保证全局最优。这跟随机初始化种子有关跑多次选代价最小的结果才是实际工程中的常用策略。注意虽然机器学习在算法笔试里占比不高但千万别直接放弃这几道题往往是拉分的关键。把SVM的核函数参数、决策树的划分指标、K-Means的收敛性这几个常见概念背下来比刷十道中等难度的LeetCode性价比要高得多。3. 编程题完整实现与边界处理3.1 笔试第一题KMP字符串匹配的改造版这题的原题大致是给定一个文本串T和一个模式串P在T中找P出现的所有起始位置要求返回一个列表。表面上就是标准KMP但有一个坑点——模式串中可能包含通配符?且?可以匹配任意单个字符。这个变体让原本标准的next数组计算失效了。我的思路是保留KMP的框架但next数组的生成逻辑要调整。当模式串中的字符是?时它和任何字符都相等所以next比较时需要考虑通配符。具体实现如下#include iostream #include vector #include string using namespace std; vectorint buildNextWithWildcard(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j] p[i] ! ? p[j] ! ?) { j next[j - 1]; } if (p[i] p[j] || p[i] ? || p[j] ?) { j; } next[i] j; } return next; } vectorint kmpMatchWithWildcard(const string t, const string p) { vectorint res; int n t.size(), m p.size(); if (m 0) return res; vectorint next buildNextWithWildcard(p); for (int i 0, j 0; i n; i) { while (j 0 t[i] ! p[j] p[j] ! ?) { j next[j - 1]; } if (t[i] p[j] || p[j] ?) { j; } if (j m) { res.push_back(i - m 1); j next[j - 1]; } } return res; }这里有个关键细节当模式串中某个字符是?时它既可以匹配任意文本串字符也可以在next数组构建时兼容其他模式串字符。所以我将模式串中的?视为一种可以被任意字符匹配的占位符比较时只要有一个是?就认为相等。这样匹配过程就可以正确识别出通配符。3.2 笔试第二题跳跃游戏II变种与贪心边界这道题我在之前章节已经提到了就是求最少跳跃次数。标准的贪心解法如下#include vector #include algorithm using namespace std; int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; int steps 0; int curEnd 0; int curFarthest 0; for (int i 0; i n - 1; i) { curFarthest max(curFarthest, i nums[i]); if (i curEnd) { steps; curEnd curFarthest; if (curEnd n - 1) break; } } return steps; }这里最容易犯的错误就是我踩过的没有处理n为1的情况。如果数组只有一个元素你已经站在最后一个位置了不需要跳跃应该返回0。如果不加这个判断代码进入循环后curEnd是0i的循环条件i n - 1直接不成立steps保持0其实也能返回0。这么看好像不加也没事但如果你把循环条件写成i n那就会算出1次跳跃直接错。另一个细节是curFarthest的更新时机。它必须在遍历每个位置时都更新而不是只在到达边界时更新。因为即使当前还没跳出这一步的范围也要提前计算下一步最远能到达哪。只有等i到达了curEnd才真正进入下一步步数加一同时把边界推进到curFarthest。3.3 快速幂与堆排序的手写模板这套卷子的选择题里虽然没有直接让手写代码但我在复盘时发现像快速幂、堆排序这种“高频手写题”虽然没有直接考但是如果不熟练掌握后面写它们的应用变形就特别容易卡壳。快速幂的核心思想是二分幂利用指数的二进制表示来减少乘法次数。它的应用场景非常多比如计算大数幂取模、矩阵快速幂等。标准模板如下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; }堆排序的重点是建堆和下滤操作。对于笔试来说手写堆排序不是很常考但实现堆排序的过程可以帮助你理解优先队列的底层实现而优先队列本身在各类算法题中出场率极高。#include vector #include algorithm using namespace std; void heapify(vectorint arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }3.4 常见边界条件整理根据这次笔试和后续复盘我把常见易漏的边界条件整理如下这些都是我实际踩过或看别人踩过的坑题型容易漏掉的边界条件错误后果数组类DP输入数组长度为0或1访问越界或返回错误值字符串匹配模式串为空字符串应该返回空列表或0二分查找目标值小于左边界或大于右边界返回-1时判断错误链表操作头节点为空或只有一个节点空指针异常树遍历根节点为空函数直接崩溃二分图匹配图可能不连通漏匹配部分节点这些都是笔试中最容易丢分的点因为大厂笔试编译环境一般不会提供详细报错信息只在最后显示通过率百分比。比如我只看到“通过73%”根本不知道是哪个用例出了问题只能自己一点点排查。4. 答题策略与时间分配技巧4.1 选择题的快速判断策略小米这套卷子的选择题里有些题目不看选项本身的话会思考很久但如果你掌握了一些“快速排除法”就能大幅提速。以排序算法复杂度为例遇到问平均复杂度是O(n log n)的排序算法可以直接锁定快排、归并、堆排序这三个如果问不稳定排除归并、插入和冒泡即可。通过这种逻辑缩小范围往往能在一分钟内解决一道原本需要背诵的题。另一个技巧是在遇到不确定的机器学习题时优先选择“训练数据足够多”这一类的答案。因为很多机器学习概念题本质上是在考“过拟合”和“欠拟合”的判断而谁更容易过拟合、谁对数据量更敏感其实是有规律可循的。选择题时间控制在30分钟以内是合理的。如果某道题卡了超过3分钟果断先标记上跳过最后再有时间回来推敲。我在做卷时就因为在一道KMP计算题上反复验算太久导致后续编程题时间紧张这个教训值得吸取。4.2 编程题的优先级分配两道编程题的难度其实是有梯度的第一道KMP变种明显比第二道贪心跳跃题难。我发现不少人上来就死磕第一题导致第二题连题都没看完就交卷了。正确的做法是先花2分钟快速浏览两题的题目判断哪道题思路更清晰先写那道。在实际笔试中我的策略是先把第二题的贪心解法写了确保能拿下一道题的分数再回头啃第一题。事实证明这个策略是对的因为第二题我花了15分钟就完成了主体逻辑和自测而第一题最终只完成了next数组构建匹配部分的通配符判断没调通。如果两道题都写不完那就优先保证“算法思路清晰、代码结构完整、部分用例能过”因为大厂笔试是机器判题按用例通过比例给分不是零分一票否决。4.3 监考环境下如何自测和定位问题笔试环境跟本地IDE的区别在于你没法打断点也很少能拿到完整报错信息。我后来养成的习惯是在提交前做三件事第一检查所有数组下标是否越界尤其是循环里用到size()减一的地方第二确认输入为空、长度为1等极端情况能否正常返回第三复读一遍题目看输出格式是否符合要求比如要求空格分隔还是换行分隔。当时第二题我漏掉的就是第一个检查项没有在循环里提前判断数组长度对步数的影响。如果你在提交前能保持这个习惯很多低级错误是可以当场发现的。5. 复盘心得与后续备赛建议5.1 小米算法笔试风格总结经过这场笔试和后续准备我总结了小米算法笔试的几个鲜明风格一是特别爱考字符串匹配KMP或者基于KMP的变种题出场率极高二是选择题非常注重算法原理深度不满足于“会调用”而是考“懂原理”三是编程题整体难度中等但坑点设计得很细节专门考验人的细心程度。这种风格跟有些大厂上来就是LeetCode Hard的套路完全不同它更在意你是不是一个基础扎实、思维严谨的人。所以在准备小米笔试时不要一味刷难题把经典数据结构和基础算法的每个细节都吃透比做一百道Hard都管用。5.2 针对性的高效备赛路线如果你距离笔试还有两周以上建议按照以下路线准备第一阶段前三天把数据结构课本过一遍重点看栈、队列、链表、树、图的基本操作和复杂度。这一阶段不刷题只看书和博客把底层原理吃透。第二阶段中间五天专项刷LeetCode热题100中的简单和中等题尤其是字符串、数组、DP这三个类别。每道题都要能自己推导出时间复杂度和空间复杂度。第三阶段最后三天专门做mock笔试和模拟题到各大刷题网站找企业真题卷来做限时训练。模拟环境很重要能让你提前感受笔试的压迫感和时间分配。5.3 我踩过的坑与修正方案最后分享几个我实际踩过的坑。第一个坑是过度依赖IDE的自动化提示笔试环境里没有代码补全后手写代码速度明显下降。解决办法是平时在手机上用备忘录写代码锻炼裸写能力特别是KMP、堆排序这种模板题。第二个坑是忽视位运算的优化。小米试卷里有一道题是关于判断整数是否为2的幂如果用循环除以2会超时但用n 0 (n (n - 1)) 0可以O(1)解决。这种常见技巧在笔试中非常实用。第三个坑是做题时不标注中间结果导致后面检查时看不出来哪一步开始错了。我现在写算法题都会在关键节点加注释或者临时输出中间变量验证这个方法在笔试中虽然不常用但非常推荐引入到平时的练习中。第四个坑是心态问题我第一题卡了太久导致后面整个节奏都乱了。后来我把做笔试题的节奏调整成“先浏览全卷再分块研究最后集中攻克”这个习惯让我后续在多家公司的笔试中稳定发挥。我个人在实际操作中最深的体会是小米这套算法卷看起来知识点很杂但只要把KMP、排序、DP、贪心、图论这几个板块的基础原理吃透再养成严谨的边界条件检查习惯通过率就能有质的提升。希望这篇复盘能帮你在下次笔试时少踩一些我踩过的坑。
秋招算法岗笔试复盘：KMP、堆排序与贪心DP核心考点全解析
作为一名参加过2022年秋招、被小米算法卷实打实虐过一遍的过来人看到这个标题我DNA都动了。这份卷子在当时算得上是几家大厂里风格比较鲜明的一套它不纯粹考刷题量而是很看重基础算法原理的深度和代码实现的严谨度。哪怕放到现在里面涉及的考点依然是面试和笔试的高频核心像KMP的next数组、堆排序的手写、贪心和动态规划的辨析几乎每家大厂笔试都会换着法子考。这篇文章我就把这份卷子的整体结构、核心题目拆解、代码实现以及我踩过的坑完整复盘一遍希望能帮准备算法岗笔试的朋友少走弯路。1. 笔试整体拆解与考点分析1.1 题型构成与考察形式2022年小米秋招算法岗笔试的卷2整体题量属于中等偏上我记得好像是单选、多选混合的选择题大概20道左右加上两道编程大题总时长在90分钟到120分钟之间。这个体量设计得很刁钻它不指望你把所有题都写完而是通过这种题量分布来区分「刷题机器」和「真正理解算法本质的人」。选择题的考察范围非常广从数据结构、排序算法、图论、动态规划到机器学习基础都有涉及。这跟纯刷LeetCode的考核方式完全不同它更偏向于考察你对算法原理的「理解深度」而非「调用能力」。比如它不会直接让你写一个排序而是问你快速排序在某种特定输入下的最坏时间复杂度是多少或者堆排序的建堆过程具体发生了多少次比较。编程题部分则回归了传统笔试风格两道题都属于“看一眼知道考什么但动手写就容易翻车”的类型。一道是字符串处理相关的KMP变种题另一道是结合了贪心思想的数组操作题。这两道题我没有当场AC完整第二题只过了部分测试用例后来复盘才发现是边界条件漏判了这部分我会在后面章节详细展开。1.2 核心考点分布与难度评估我把这套卷子涉及的核心考点按出现频次和难度整理成了一个表格方便大家直观感受备考优先级考点类别具体知识点出现频次难度评估字符串匹配KMP算法、next数组计算高中等排序算法快排、堆排、归并的复杂度与稳定性高低-中等动态规划经典DP模型、状态转移推导高中高贪心算法经典贪心场景辨析中中等图论算法最短路径、最小生成树中中等机器学习SVM、决策树、聚类基础概念低低数学基础快速幂、位运算中低从这个分布也能看出小米的算法笔试风格其实很像“考研408 LeetCode热题100”的混合体。数据结构基础扎实的同学会占很大优势而那些只刷题不看书的人反而容易在选择题上翻车。另外我注意到一个细节卷子里出现了KL散度相关的选择题虽然热搜词里很多人搜的是“KL ELBO算法原理详解”但笔试实际考察的并不深只是问KL散度是否为对称度量以及它在变分推断里的基本作用。这说明它不是想考你推导而是看你了不了解这个概念本身。提示如果你准备时间有限重心一定要放在字符串匹配、排序、DP和贪心上机器学习相关概念只要把常见模型的优缺点背熟即可不会出太偏的题。2. 高频算法题逐一拆解与答题思路2.1 KMP算法的next数组计算与失配指针原理这份卷子的选择题里有一道很经典的题给定模式串“abacaba”要求计算它的next数组。这个字符串我印象太深了因为它在KMP学习里属于非常具有代表性的例子包含了前缀后缀的嵌套关系。先回忆一下next数组的定义next[i]表示模式串前i个字符组成的子串中最长相等前缀后缀的长度通常不包含自身即长度小于i。计算“abacaba”的next数组过程是这样的i1时子串“a”没有真前缀和真后缀next[1]0i2时子串“ab”前缀“a”和后缀“b”不匹配next[2]0i3时子串“aba”前缀“a”与后缀“a”匹配长度为1next[3]1i4时子串“abac”最长相等前缀后缀为0next[4]0i5时子串“abaca”前缀“a”和后缀“a”匹配长度为1next[5]1i6时子串“abacab”前缀“ab”和后缀“ab”匹配长度为2next[6]2i7时子串“abacaba”前缀“aba”和后缀“aba”匹配长度为3next[7]3。所以最终next数组是[0, 0, 1, 0, 1, 2, 3]。这道题如果理解透彻了30秒内就能算完。但如果你只是记住了代码模板而不理解原理遇到这种稍微变形一点的问题就容易懵。KMP的核心思想就是利用已经匹配的部分信息让模式串在失配时可以向右滑动尽可能远的距离。next数组保存的正是这个“滑动距离”的依据。面试时如果被追问还会让你解释为什么next数组能保证不漏匹配这就涉及到了失配时的“安全位移”概念。笔试虽然不考推导但考计算能力所以一定要多手动推导几个字符串的next数组练出手感。2.2 排序算法复杂度、稳定性与适用场景对比排序算法在小米这套卷子里占比不低而且考察方式非常灵活。选择题里直接考了堆排序建堆的比较次数、快速排序在已经有序数组上的表现、归并排序的空间复杂度等。关于堆排序有一个容易错的知识点建堆的时间复杂度不是一个一个插入的O(n log n)而是O(n)。原因是自底向上的下滤操作大部分节点都不会下沉太深。选择题里如果问建堆复杂度一定要选O(n)而不是O(n log n)。快速排序的退化场景也是一大考点。当输入数组已经有序或者逆序时如果每次选的基准都是首元素或尾元素那分区极度不平衡递归深度变成n时间复杂度退化到O(n²)。这也是为什么实际工程中会用随机化快排或三数取中法来避免这个情况。关于稳定性我在备考时专门做了个总结表笔试选择题直接套用就行排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)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²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定这套表看似简单但真正的考点在于组合比如“统计一个数组中有多少逆序对用什么排序思想可以在O(n log n)内解决”答案是归并排序再比如“如果数组基本有序选择哪个排序算法效率最高”答案是插入排序因为它的最好情况是O(n)。这些都是小米选择题的常见变形。2.3 动态规划与贪心策略的典型题目辨析动态规划和贪心是算法笔试中的“重头戏”这套卷子的选择题里出现了好几道编程题里也有一道。它们之间的核心区别在于贪心算法每一步做局部最优选择期望能达到全局最优动态规划则通过穷举所有子问题并记录最优结果来保证全局最优。选择题里有一道非常经典的辨析题给定一组区间问如何选择最多数量的互不重叠区间。这道题的正解是贪心——按照区间结束时间排序每次选择结束最早且与前面不冲突的区间。但如果把题目改成“选择区间使得覆盖总长度最大”贪心就不成立了需要动态规划。小米这类题考得就是这个“能否识别出贪心不适用场景”的能力。我还记得编程题第二道就是类似“跳跃游戏II”的变种给定一个非负整数数组每个元素代表从当前位置最多能跳多远问最少跳几次能跳到最后一个位置。这道题贪心可以解需要维护当前跳跃能达到的边界和下一步能达到的最远位置。核心思路是在当前步的覆盖范围内遍历不断更新下一步能达到的最远位置当遍历到当前边界时步数加一。边界条件是数组长度为1时返回0这个条件我当时漏了导致部分用例不过。2.4 图论算法最短路径与最小生成树的考点图论这部分小米卷2考了一道关于Dijkstra算法的选择题问的是在什么情况下Dijkstra算法会失效。正确答案是当图中存在负权边时Dijkstra基于贪心策略的假设会被打破。这个知识点几乎每家公司的算法笔试都会考因为很多人只背了代码却没想过为什么它不能处理负权边。另外还考了最小生成树具体题目是问Kruskal算法和Prim算法的适用场景区别。Kruskal按边权重从小到大排序适合稀疏图边数远小于顶点数平方的图Prim按点逐步扩张适合稠密图。这个区分点很关键我把它记成了“Kruskal管边Prim管点”。如果你能把这两个算法各自的优化方式也搞明白——比如Prim可以用优先队列优化Kruskal依赖并查集——那选择题基本就不会失分了。还有一道题涉及Kahn算法即拓扑排序的BFS实现方法。考察的是入度为零的节点依次入队的过程以及当图中有环时队列会提前为空的现象。这道题的变形做法是通过Kahn算法统计出队节点数量如果小于总节点数则说明图中存在环。2.5 机器学习基础SVM、决策树与聚类的浅层考察小米算法笔试卷里居然混进了几道机器学习相关的选择题这一点当时让不少只刷算法题的同学措手不及。虽然题目难度不大但如果你完全没接触过就只能靠蒙。有一道题是问SVM的核函数中哪个参数控制模型复杂度。答案是gamma。gamma越小高斯核函数的作用范围越大决策边界越平滑gamma越大每个训练样本的影响范围越小越容易过拟合。这道题属于典型的面试概念题不需要推导公式但需要理解参数含义。还有一道关于决策树特征选择的题问的是信息增益在有多个取值特征的场景下容易偏向哪种特征。答案是取值多的特征。如果属性类别过多每个分支下的样本会很少纯度会异常地高因此信息增益会产生偏好。这种问题的正解通常是采用增益率来校正这也是C4.5算法的改进动机。聚类的题考的是K-Means的收敛行为问其目标函数是什么以及是否一定能收敛到全局最优。答案是它能保证收敛到局部最优但不保证全局最优。这跟随机初始化种子有关跑多次选代价最小的结果才是实际工程中的常用策略。注意虽然机器学习在算法笔试里占比不高但千万别直接放弃这几道题往往是拉分的关键。把SVM的核函数参数、决策树的划分指标、K-Means的收敛性这几个常见概念背下来比刷十道中等难度的LeetCode性价比要高得多。3. 编程题完整实现与边界处理3.1 笔试第一题KMP字符串匹配的改造版这题的原题大致是给定一个文本串T和一个模式串P在T中找P出现的所有起始位置要求返回一个列表。表面上就是标准KMP但有一个坑点——模式串中可能包含通配符?且?可以匹配任意单个字符。这个变体让原本标准的next数组计算失效了。我的思路是保留KMP的框架但next数组的生成逻辑要调整。当模式串中的字符是?时它和任何字符都相等所以next比较时需要考虑通配符。具体实现如下#include iostream #include vector #include string using namespace std; vectorint buildNextWithWildcard(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j] p[i] ! ? p[j] ! ?) { j next[j - 1]; } if (p[i] p[j] || p[i] ? || p[j] ?) { j; } next[i] j; } return next; } vectorint kmpMatchWithWildcard(const string t, const string p) { vectorint res; int n t.size(), m p.size(); if (m 0) return res; vectorint next buildNextWithWildcard(p); for (int i 0, j 0; i n; i) { while (j 0 t[i] ! p[j] p[j] ! ?) { j next[j - 1]; } if (t[i] p[j] || p[j] ?) { j; } if (j m) { res.push_back(i - m 1); j next[j - 1]; } } return res; }这里有个关键细节当模式串中某个字符是?时它既可以匹配任意文本串字符也可以在next数组构建时兼容其他模式串字符。所以我将模式串中的?视为一种可以被任意字符匹配的占位符比较时只要有一个是?就认为相等。这样匹配过程就可以正确识别出通配符。3.2 笔试第二题跳跃游戏II变种与贪心边界这道题我在之前章节已经提到了就是求最少跳跃次数。标准的贪心解法如下#include vector #include algorithm using namespace std; int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; int steps 0; int curEnd 0; int curFarthest 0; for (int i 0; i n - 1; i) { curFarthest max(curFarthest, i nums[i]); if (i curEnd) { steps; curEnd curFarthest; if (curEnd n - 1) break; } } return steps; }这里最容易犯的错误就是我踩过的没有处理n为1的情况。如果数组只有一个元素你已经站在最后一个位置了不需要跳跃应该返回0。如果不加这个判断代码进入循环后curEnd是0i的循环条件i n - 1直接不成立steps保持0其实也能返回0。这么看好像不加也没事但如果你把循环条件写成i n那就会算出1次跳跃直接错。另一个细节是curFarthest的更新时机。它必须在遍历每个位置时都更新而不是只在到达边界时更新。因为即使当前还没跳出这一步的范围也要提前计算下一步最远能到达哪。只有等i到达了curEnd才真正进入下一步步数加一同时把边界推进到curFarthest。3.3 快速幂与堆排序的手写模板这套卷子的选择题里虽然没有直接让手写代码但我在复盘时发现像快速幂、堆排序这种“高频手写题”虽然没有直接考但是如果不熟练掌握后面写它们的应用变形就特别容易卡壳。快速幂的核心思想是二分幂利用指数的二进制表示来减少乘法次数。它的应用场景非常多比如计算大数幂取模、矩阵快速幂等。标准模板如下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; }堆排序的重点是建堆和下滤操作。对于笔试来说手写堆排序不是很常考但实现堆排序的过程可以帮助你理解优先队列的底层实现而优先队列本身在各类算法题中出场率极高。#include vector #include algorithm using namespace std; void heapify(vectorint arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }3.4 常见边界条件整理根据这次笔试和后续复盘我把常见易漏的边界条件整理如下这些都是我实际踩过或看别人踩过的坑题型容易漏掉的边界条件错误后果数组类DP输入数组长度为0或1访问越界或返回错误值字符串匹配模式串为空字符串应该返回空列表或0二分查找目标值小于左边界或大于右边界返回-1时判断错误链表操作头节点为空或只有一个节点空指针异常树遍历根节点为空函数直接崩溃二分图匹配图可能不连通漏匹配部分节点这些都是笔试中最容易丢分的点因为大厂笔试编译环境一般不会提供详细报错信息只在最后显示通过率百分比。比如我只看到“通过73%”根本不知道是哪个用例出了问题只能自己一点点排查。4. 答题策略与时间分配技巧4.1 选择题的快速判断策略小米这套卷子的选择题里有些题目不看选项本身的话会思考很久但如果你掌握了一些“快速排除法”就能大幅提速。以排序算法复杂度为例遇到问平均复杂度是O(n log n)的排序算法可以直接锁定快排、归并、堆排序这三个如果问不稳定排除归并、插入和冒泡即可。通过这种逻辑缩小范围往往能在一分钟内解决一道原本需要背诵的题。另一个技巧是在遇到不确定的机器学习题时优先选择“训练数据足够多”这一类的答案。因为很多机器学习概念题本质上是在考“过拟合”和“欠拟合”的判断而谁更容易过拟合、谁对数据量更敏感其实是有规律可循的。选择题时间控制在30分钟以内是合理的。如果某道题卡了超过3分钟果断先标记上跳过最后再有时间回来推敲。我在做卷时就因为在一道KMP计算题上反复验算太久导致后续编程题时间紧张这个教训值得吸取。4.2 编程题的优先级分配两道编程题的难度其实是有梯度的第一道KMP变种明显比第二道贪心跳跃题难。我发现不少人上来就死磕第一题导致第二题连题都没看完就交卷了。正确的做法是先花2分钟快速浏览两题的题目判断哪道题思路更清晰先写那道。在实际笔试中我的策略是先把第二题的贪心解法写了确保能拿下一道题的分数再回头啃第一题。事实证明这个策略是对的因为第二题我花了15分钟就完成了主体逻辑和自测而第一题最终只完成了next数组构建匹配部分的通配符判断没调通。如果两道题都写不完那就优先保证“算法思路清晰、代码结构完整、部分用例能过”因为大厂笔试是机器判题按用例通过比例给分不是零分一票否决。4.3 监考环境下如何自测和定位问题笔试环境跟本地IDE的区别在于你没法打断点也很少能拿到完整报错信息。我后来养成的习惯是在提交前做三件事第一检查所有数组下标是否越界尤其是循环里用到size()减一的地方第二确认输入为空、长度为1等极端情况能否正常返回第三复读一遍题目看输出格式是否符合要求比如要求空格分隔还是换行分隔。当时第二题我漏掉的就是第一个检查项没有在循环里提前判断数组长度对步数的影响。如果你在提交前能保持这个习惯很多低级错误是可以当场发现的。5. 复盘心得与后续备赛建议5.1 小米算法笔试风格总结经过这场笔试和后续准备我总结了小米算法笔试的几个鲜明风格一是特别爱考字符串匹配KMP或者基于KMP的变种题出场率极高二是选择题非常注重算法原理深度不满足于“会调用”而是考“懂原理”三是编程题整体难度中等但坑点设计得很细节专门考验人的细心程度。这种风格跟有些大厂上来就是LeetCode Hard的套路完全不同它更在意你是不是一个基础扎实、思维严谨的人。所以在准备小米笔试时不要一味刷难题把经典数据结构和基础算法的每个细节都吃透比做一百道Hard都管用。5.2 针对性的高效备赛路线如果你距离笔试还有两周以上建议按照以下路线准备第一阶段前三天把数据结构课本过一遍重点看栈、队列、链表、树、图的基本操作和复杂度。这一阶段不刷题只看书和博客把底层原理吃透。第二阶段中间五天专项刷LeetCode热题100中的简单和中等题尤其是字符串、数组、DP这三个类别。每道题都要能自己推导出时间复杂度和空间复杂度。第三阶段最后三天专门做mock笔试和模拟题到各大刷题网站找企业真题卷来做限时训练。模拟环境很重要能让你提前感受笔试的压迫感和时间分配。5.3 我踩过的坑与修正方案最后分享几个我实际踩过的坑。第一个坑是过度依赖IDE的自动化提示笔试环境里没有代码补全后手写代码速度明显下降。解决办法是平时在手机上用备忘录写代码锻炼裸写能力特别是KMP、堆排序这种模板题。第二个坑是忽视位运算的优化。小米试卷里有一道题是关于判断整数是否为2的幂如果用循环除以2会超时但用n 0 (n (n - 1)) 0可以O(1)解决。这种常见技巧在笔试中非常实用。第三个坑是做题时不标注中间结果导致后面检查时看不出来哪一步开始错了。我现在写算法题都会在关键节点加注释或者临时输出中间变量验证这个方法在笔试中虽然不常用但非常推荐引入到平时的练习中。第四个坑是心态问题我第一题卡了太久导致后面整个节奏都乱了。后来我把做笔试题的节奏调整成“先浏览全卷再分块研究最后集中攻克”这个习惯让我后续在多家公司的笔试中稳定发挥。我个人在实际操作中最深的体会是小米这套算法卷看起来知识点很杂但只要把KMP、排序、DP、贪心、图论这几个板块的基础原理吃透再养成严谨的边界条件检查习惯通过率就能有质的提升。希望这篇复盘能帮你在下次笔试时少踩一些我踩过的坑。 
