小米2019秋招算法笔试题A卷全解析：从KMP到动态规划

一年一度的秋招又要开始了算法岗笔试题永远是大家最头疼的关卡。翻出我自己当年整理的小米2019秋招算法笔试题A卷发现很多思路直到今天依然适用。这份试卷覆盖了数据结构、字符串匹配、动态规划、机器学习基础等多个维度题量不算小难度梯度拉得也比较开。无论你准备投递小米还是其他一线大厂的算法岗这份A卷都值得拿出来逐题拆一遍既能用来检验自己刷题阶段的盲区也能提前适应笔试的出题风格和节奏。我会从试卷整体结构出发把高频考点的底层原理、手算推导、代码实现到考场上的排错经验都过一遍。特别是KMP算法中next数组的手算过程、动态规划状态定义这类容易卡壳的地方我会用最直观的方式讲透。文章尽量少讲虚的能实操的全部给出可直接套用的方案。1. 试卷整体结构与题目设计思路拆解1.1 小米算法岗笔试的题型布局小米2019秋招算法笔试题A整体分为三块单选题、多选题和编程题。单选多选加起来大概接近30道覆盖数据结构、算法分析、概率统计、机器学习基础编程题通常是2道左右难度分布为一道中等偏易、一道中等偏难。考试总时长一般在60到90分钟对做题速度的要求比较高。从实际考试反馈来看选择题的题干并不啰嗦但陷阱设计得很细比如栈和队列的操作顺序、排序算法稳定性的判断、哈希表冲突处理的平均查找长度、神经网络中感受野的计算等。这些知识点单看都不难但放在限时场景下很容易因为粗心丢分。编程题则更看重代码实现的完整性与边界处理能力光有思路但代码跑不过测试用例一样拿不到分。1.2 设计逻辑为什么这样出题大厂算法岗位的笔试本质上是“成本最低的筛选器”。面试官在几百份简历中需要快速判断候选人的基本功和代码敏感度选择题能高效考察知识点的广度而编程题则直接模拟日常开发中会遇到的问题抽象、算法设计与实现验证流程。另一个值得注意的点是小米的业务线覆盖IoT、智能手机、智能汽车、互联网服务等多个方向算法岗位可能涉及图像处理、推荐系统、NLP、语音识别等具体场景。因此试卷里会出现一些和业务强相关的题目比如海量数据排序、TopK问题、字符串匹配这类在日志分析、搜索推荐中高频使用的算法而不是纯粹从《算法导论》里抽题。理解了这一点复习方向就会更明确基础数据结构要熟练经典算法要能手写复杂度和边界分析要形成肌肉记忆。1.3 时间分配与答题顺序建议我的建议是选择题控制在20分钟内遇到卡壳超过2分钟的题先标记跳过不要恋战多选题要格外谨慎少选一般比多选安全编程题至少留出35分钟。先做自己有把握的编程题再做另一道保证至少AC一道题比两道题都写一半要划算得多。特别是遇到代码量大、题意复杂的题先花3分钟把输入输出格式和样例跑通再开始写核心逻辑。很多时候不是算法本身难而是理解错了题意导致白费功夫。2. 高频算法考点的原理解析与手算示范2.1 KMP算法的next数组到底怎么算字符串匹配是算法笔试的常客而KMP算法中next数组的手算推导更是每年必考的热点。这次的网络热词里出现了“对于模式串p‘abacaba’其next数组”这个问题我就拿它来示范一遍完整推导过程。先说清楚定义。题目里常见的next数组有两种定义方式定义一next[i]表示模式串p[0...i-1]的最长相等真前缀与真后缀长度规定next[0] -1next[1] 0。定义二next[i]表示模式串p[0...i]的最长相等真前缀与真后缀长度即失配时参照的位置。以p abacaba为例按下标从0开始逐个计算子串范围对应子串最长相等真前后缀next值定义一next值定义二p[0...0]a无-10p[0...1]ab无00p[0...2]abaa11p[0...3]abac无00p[0...4]abacaa11p[0...5]abacabab22p[0...6]abacabaaba33所以采用定义一时next数组为[-1, 0, 0, 1, 0, 1, 2, 3]采用定义二时结果为[0, 0, 1, 0, 1, 2, 3]。两种定义都不影响匹配时的跳转逻辑只是数组下标偏移不同答题前务必看清楚题目用的是哪一种别在这种地方白丢分。手工计算的经验是先写出每个前缀子串再找最长相同前后缀。注意真前缀和真后缀不能等于整个子串本身很多同学一开始会在这里出错。比如aba的最长相等真前后缀是a长度为1而不是aba。2.2 排序算法复杂度对比与手写要点排序算法是选择题的常客尤其爱考稳定性、时间复杂度和手写实现中的细节。我把最常出现的几种整合成一张表。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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^2)O(n^2)O(1)稳定希尔排序O(n^1.3)左右O(n^2)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定手写快速排序时最容易翻车的是partition部分。我建议直接用最经典的Lomuto分区或Hoare分区不要在考场上临场发明新写法。Lomuto分区简单直观适合笔试Hoare分区常数更小但边界条件更绕容易写错。另一个高频考点是堆排序的下滤操作很多人在构建初始堆时忘记从最后一个非叶子节点开始调整导致整个堆结构错误。2.3 贪心、动态规划与二分搜索怎么选看到一道题第一步不是想着套模板而是判断它属于哪类问题。如果题目问的是最值、方案数、可行性判断大概率是动态规划或二分答案如果贪心策略可以用反证法证明局部最优能推出全局最优才选择贪心如果问题具有单调性比如在有序数组上查找、求满足条件的最短/最长长度二分搜索往往是最优解。一个很实用的判断方法先写暴力递归看是否存在重叠子问题。如果存在就考虑用记忆化搜索或动态规划优化如果递归结构天然具有单调性再考虑二分答案。动态规划的状态定义是核心不要一上来就套背包、区间DP等模板。笔试题目往往包装在具体场景里需要先把场景抽象成状态转移方程再决定用哪种DP类型。3. 典型笔试题的实操推演与代码实现3.1 一道经典编程真题题面复现与暴力解编程题部分我挑一道具有代表性的题来完整演示给定一个只包含0和1的二进制数组找到含有相同数量的0和1的最长连续子数组的长度。比如输入[0, 1, 0, 1, 0]输出应为4因为[0, 1, 0, 1]中0和1各出现两次。看到这道题第一反应是暴力枚举所有子数组判断每个子数组内0和1的数量是否相等。复杂度O(n^2)能把样例跑通但数据量一大就会超时不是理想解法。3.2 从暴力到最优的优化过程怎么优化把0看成-11看成1问题就转化为“找到和为0的最长连续子数组”。这就要用到前缀和加上哈希表的套路。具体来说遍历数组时维护一个前缀和count每遇到1就加1遇到0就减1。如果某个前缀和之前出现过说明从上次出现位置到当前位置之间的子数组和为0即0和1数量相等。用哈希表记录每个前缀和第一次出现的位置每次碰到重复前缀和就用当前位置减去第一次出现位置更新答案。这里的关键是哈希表初始化时要先把0位置设置为-1。因为前缀和为0的最早出现位置可以理解为在数组起始之前这样才能覆盖整个数组从头开始计算的情况。这个细节非常容易漏。3.3 完整代码与复杂度分析最终实现如下def findMaxLength(nums): count 0 first_occurrence {0: -1} max_len 0 for i, num in enumerate(nums): if num 1: count 1 else: count - 1 if count in first_occurrence: max_len max(max_len, i - first_occurrence[count]) else: first_occurrence[count] i return max_len时间复杂度O(n)空间复杂度O(n)。这个解法在笔试中属于必须拿下的水平因为思路典型、实现简单也是后续很多子数组类问题的原型比如和为K的最长子数组等理解了前缀和加哈希的原理后可以一法通百法通。3.4 机器学习与深度学习基础题补遗除了纯算法题小米的算法笔试A卷里还会出现几道机器学习相关的题目。高频考点包括正则化为什么能防止过拟合L1正则化相当于在损失函数上施加了拉普拉斯先验L2正则化相当于高斯先验它们都限制了模型参数的空间。类别不平衡时为什么不能只看准确率准确率在正负样本比例悬殊时会产生误导应结合精确率、召回率、F1值以及AUC进行综合评估。梯度下降中学习率的影响学习率过大会震荡不收敛过小则收敛速度慢实际调参时可以结合学习率衰减策略。这些题目不需要背很深的数学推导但概念辨析要清楚。特别要注意多选题容易出现的干扰项比如“L2正则化会让模型参数变为0”“随机森林一定比决策树好”这类绝对化的说法基本都是错误选项。4. 笔试环境下的答题策略与防坑清单4.1 输入输出格式大厂笔试最容易扣分的地方很多人刷LeetCode习惯了核心代码模式一到牛客网或赛码网就栽在输入输出上。小米笔试通常采用ACM风格需要自己处理输入解析。这里有几个很实用的经验优先用sys.stdin.readline()读取行避免input()在循环读大量数据时拖慢速度。不确定一行有几个整数时用split()后自动适配长度。输出格式严格要求比如每个结果占一行、保留几位小数、行尾不能有多余空格都要看清楚。4.2 边界条件与极端用例自查写完代码不要急着提交先在心里跑几组边界用例数组长度为0或1时是否直接返回正确值。数字是否可能为负数负数对前缀和算法的影响。目标值不存在时二分搜索的边界是否会出现死循环。是否需要对输入进行排序排序后原结果的顺序是否会受影响。这些边界条件往往决定了一道题是从全对变成部分通过还是从部分通过变成零分。笔试判题通常按通过用例比例给分边界用例挂掉非常可惜。4.3 常见失分点整理表我把自己踩过的坑和身边同学常犯的错误整理成一张速查表考试前扫一眼很有帮助。失分点典型场景应对方案未初始化哈希表首位前缀和类问题漏掉{0: -1}先手动模拟一遍从下标0开始的完整区间多重循环变量写错快排、归并的索引边界用具体小数组走一遍循环浮点数精度问题二分答案判断改用固定迭代次数或误差阈值误用sort改变原数组后续还需原始顺序使用切片复制arr[:]递归深度超限链表反转、树的遍历改为迭代栈实现状态转移方向错误DP数组填充顺序画表确认依赖方向4.4 选择题中的“直觉陷阱”选择题里有一类题专门考验直觉。比如问“在哈希表中线性探测法在什么情况下性能急剧下降”答案不是“哈希函数设计不好”而是“装载因子接近1”。很多同学凭直觉选了哈希函数实际上真正导致性能崩塌的是装载因子过高。处理这类问题最好的办法是建立“量化思维”。不要停留在“快一点”“慢一点”这种定性描述上面试官希望看到你能说出平均时间复杂度、最坏复杂度和触发条件。复习每个算法时都问自己三个问题最好情况是什么最坏情况是什么哪种输入会触发最坏情况5. 复盘心得与后续扩展5.1 从这份考卷里提炼出的刷题优先级结合小米这份A卷和近几年的秋招趋势算法岗笔试的复习优先级可以这样排第一梯队是数组、字符串、哈希表、链表、二叉树的基本操作与遍历。这些是笔试的地基几乎每套卷子都会考。第二梯队是动态规划、二分法、贪心、排序的变种题难度中等但出现频率极高。第三梯队是图论、并查集、Trie树、线段树这类进阶内容通常只在最后一道压轴编程题出现属于拉分题。按照这个优先级分配复习时间比盲目刷几百道LeetCode效率高得多。不是每个题都值得刷两遍把高频题型做到闭着眼能写出来性价比最高。5.2 笔试后如何高效复盘笔试结束并不是终点建议立刻把没做出来的题记录下来。不用急着看题解先自己重新思考30分钟把卡住的点写下来比如“不知道如何定义状态”“没发现前缀和性质”“边界条件遗漏”。然后再去看题解重点看别人是怎么从题目描述跳到算法思想的。根据我个人的经验真正能拉开差距的不是刷题数量而是复盘质量。一套卷子吃透三道题比草草刷完十道题效果更好。尤其是把“为什么我想不到”这个问题回答清楚比把题解背下来有用得多。5.3 最后再分享一个小技巧考试前一周不要再做新题了把所有做过的错题重新过一遍。我习惯准备一个错题本按“题目类型-错误原因-正确思路-代码模板”四栏整理。笔试前只看错题本效率远高于重新翻题单。另外很多同学忽略了的还有代码风格变量命名规范、函数拆分的清晰度虽然笔试不专门打分但整洁的代码能帮你在调试时更快定位问题这个习惯在面试手写代码环节同样重要。