春招那阵子算法岗的笔试题目总是一票难求。尤其是像小米这种体量的公司2018春季实习生招聘的算法工程师客观题在当年算是比较有代表性的考察样本。我最近翻到这份题越看越觉得它涵盖的面很典型基础数据结构、字符串处理、经典机器学习理论、深度学习概念再加上一些工程上常用的算法思想。很多准备面试的朋友问我该怎么刷题我觉得与其盲目刷LeetCode不如认真拆一份这样的客观题卷子看看出题人到底想从哪些维度考核你。这篇就当作一个亲身复盘来写针对这套小米2018春季实习生算法工程师客观题把题目背后的考察逻辑、涉及的算法原理、容易踩的坑全部梳理一遍。默认你至少学过《数据结构》和《机器学习》的基础课没学过也能看懂大部分内容只是个别名词需要自己翻书补一下。我尽量把每道题背后的为什么讲透而不是只给答案。1. 这张卷子到底考什么先看清出题人的底牌实习生的算法岗笔试通常不会像校招正职那样深挖系统设计或复杂工程场景它的核心目的是筛掉两类人一类是基础不扎实连数据结构都写不明白另一类是对机器学习原理停留在调包层面只会调用sklearn和PyTorch一扯到内部机制就发懵。小米这份客观题恰恰就在这两个方向上做文章。1.1 考察范围的四块拼图从整套题的构成看大概可以分成四个模块。第一块是数据结构与算法核心。包括字符串匹配的KMP算法、各种排序算法的复杂度与稳定性、二叉树和堆的基本操作、图论算法中的Dijkstra和拓扑排序。这块占比最大因为算法工程师不管做什么方向代码基本功是第一道门槛。最典型的就是KMP算法题目会给出一个模式串比如abacaba让你求next数组这属于送分题但也是区分度的起点。多数人只记口诀真让手推next数组就乱了这个后面我会详细展开。第二块是经典机器学习理论。考察内容包括朴素贝叶斯、KNN、决策树、支持向量机、聚类算法、集成学习方法还会涉及一些基础的概率论与统计知识。题目往往会问某个算法的适用场景、损失函数形式、正则化作用或者偏差方差权衡之类。第三块是深度学习概念。包括卷积神经网络的基本结构、激活函数、池化层作用、常见的优化器、过拟合的处理方法。2018年那会儿Transformer和BERT还没完全统治NLP圈所以深度学习的考察相对基础但也开始涉及一些工程细节比如梯度消失和梯度爆炸的问题。第四块是算法工程应用。比如PID控制算法在硬件系统里的作用、卡尔曼滤波的适用场景、BM25在搜索排序里的原理、模拟退火的收敛特性。这类题是小米这种兼具硬件和软件业务的公司的特色——算法工程师不是纯写Python做模型还可能要处理传感器数据、图像信号、甚至电机控制所以偶尔出现一些不那么互联网的算法题。1.2 出题难度和筛选逻辑这套题的难度如果按1到10打分大概在6.5分左右。比互联网大厂校招的常规笔试略简单但比纯粹的八股文要难一档。它的筛选逻辑是基础概念够不够牢固、能不能把学过的算法在具体场景中迁移、遇到没见过的题目有没有推理能力。对比同期的BAT笔试小米的题更偏向工程落地。百度喜欢考大量数学和统计推导腾讯爱考海量数据和排序而小米因为业务线复杂题目风格更多元。看到像PID算法在CRPS PSU Power中的作用这种题其实是在试探你算法工程师除了跑模型之外对系统底层控制逻辑有没有基本概念。如果你能答出来说明知识面是真的广不是只刷了几百道LeetCode就来的。2. 数据结构与算法真题精解手撕代码前的理论分这一块是客观题的大头也是最容易拉开差距的地方。很多人算法题能AC但客观题选不对核心原因就是只记代码实现不理解理论推导。我挑几个高频考点详细拆。2.1 KMP算法的next数组到底怎么推KMP几乎是笔试必考。题目会给一个模式串要求你写出next数组或者nextval数组。我记得有一道题就是给了abacaba然后列了四个不同的next数组选项。先说next数组的定义next[i]指模式串前i个字符组成的子串中最长相等前缀后缀的长度加不加1取决于版本约定。2020年以后的教材普遍采用next[i]表示最长相等前后缀长度本身而早期严蔚敏版的教材把next[0]设为-1next[i]等于最长相等前后缀长度再加1。这是最坑的地方不同教材约定不一样答案就完全不一样。以abacaba为例采用前缀函数π的约定即next[i]是前缀长度i的子串的最长公共前后缀长度从1开始编号next[1] 0子串a没有真前缀和真后缀相同。next[2] 0子串ab前缀a后缀b不相等。next[3] 1子串aba前缀a后缀a相等长度1。next[4] 0子串abac前缀aababa后缀cacbac没有一个相等。next[5] 1子串abaca前缀a和后缀a相等。next[6] 2子串abacab前缀ab和后缀ab相等。next[7] 3子串abacaba前缀aba和后缀aba相等。所以数组是[0, 0, 1, 0, 1, 2, 3]。如果按严蔚敏的版本整体加1得到[-1, 0, 0, 1, 0, 1, 2]。你做这道题之前必须明确题目里的next数组到底采用哪种约定。我在实际面试里发现这个细节能卡掉一半的人但理解原理的人根本不会被这种约定差异卡住——你只需要看清楚题干的定义。关于KMP我建议你额外掌握一个点为什么KMP是线性的本质是模式串的指针j只增不减匹配失败时j回退到next[j]的位置这个回退次数被下一个字符的成功匹配偿还因此均摊下来是O(n)。如果只记模板但不理解均摊分析一旦题目换个问法比如问最坏情况下匹配几次你就会被困住。2.2 排序算法的稳定性与复杂度最容易被钓鱼的部分这套题里至少有三四道和排序相关。出题人最爱的坑是让你判断某个排序算法的稳定性或者比较最好、最坏、平均时间复杂度。我的建议是不要背表格而是理解每一类排序的交换/插入逻辑稳定性自己推一遍。比如堆排序建堆的时候父子节点交换相等的元素可能越过其他相等的元素所以不稳定。快速排序因为分区的过程用到了左右指针交换也不稳定。而冒泡排序和插入排序因为只在相邻元素之间比较交换相等元素不会越过彼此所以稳定。归并排序在合并两个有序数组时只要把左边数组的相等元素优先放入就能保持稳定。另一个高频考点是堆排序的建堆复杂度。很多人以为建堆是O(n log n)实际上从最后一个非叶子节点开始向下调整综合计算下来是O(n)。这个O(n)的来源可以这样理解第k层的节点数为2^k每个节点最多下坠h-k层总代价是Σ(2^k × (h-k))化简后等于2^(h1) - h - 2约等于2n。这个推导在笔试中可能会以堆排序建堆的时间复杂度是多少的形式出现选O(n)就对了。还有一个经典题目是快速排序的最坏情况。当每次划分都选取到最小或最大元素作为基准时区间退化为n-1和0递归深度达到O(n)总时间复杂度O(n²)。如果你选的基准是第一个元素而输入本身是有序的就会触发最坏情况。2018年的笔试里出现过类似的场景让你判断某个输入序列下快速排序的表现这时候知道基准选取策略远比只会写快排代码重要。2.3 图算法Dijkstra、拓扑排序与Kahn算法图论部分Dijkstra算法是必考的。客观题主要问你Dijkstra能不能处理负权边。答案是不能。因为Dijkstra的贪心策略是当前距离最小的节点今后不会再被更新一旦存在负权边某个节点可能在中途被一个更大的距离弹出但它其实还有一条含负边的更短路径这就破坏了贪心假设。所以有负权边时应该用Bellman-Ford或者SPFA。Kahn算法是求拓扑序的经典方法核心逻辑很简单维护一个入度为0的节点集合每次取一个节点输出然后删除它的所有出边更新邻接节点的入度直到集合为空。如果输出节点数量不等于图的节点总数说明图里有环。笔试喜欢考Kahn算法的时间复杂度用邻接表实现时每个节点和边都只处理一次所以是O(VE)。这个复杂度很典型很多图算法只要是遍历一遍边、遍历一遍点的模式基本都是O(VE)。2018年那会儿还流行考二分图匹配的HK算法Hopcroft-Karp。这个算法可以看作是匈牙利算法的优化版通过BFS构建分层图再用DFS做多路增广时间复杂度从O(VE)优化到O(E√V)。题目可能不会要求手撕代码但会让你判断某个场景是否能建模成二分图最大匹配比如任务分配、课程安排、棋盘覆盖等。这种题考查的是建模能力而不是算法本身的实现细节。3. 机器学习客观题不在调库而在推导这套笔试的第二个重头戏是机器学习基础。每年死在机器学习客观题上的同学非常多因为大家习惯了调库一问公式就麻。我挑几个高频考点的核心原理说清楚。3.1 朴素贝叶斯、KNN和KL散度朴素贝叶斯的关键假设是条件独立它把联合概率拆成先验概率和条件概率的乘积。客观题爱考的是为什么朴素贝叶斯在特征相关性较强时表现较差。因为条件独立性假设与真实分布不符概率估计会偏差。但这不意味着朴素贝叶斯没用在文本分类这种特征独立性相对较好的场景它仍然是个强基线。与之相关的还有贝叶斯公式的应用题通常会给你一组先验概率和似然概率让你计算后验概率然后选分类。这类题不难但需要细心比如某个邮件含免费和点击两个词已知两个词各自条件下的概率求这封邮件被判为垃圾邮件的概率需要把条件独立假设代进去再算全概率公式的分母。如果漏乘了某个概率答案就会错。KNNK近邻是另一个高频概念。题目围绕K值选择和距离度量做文章。K值越小模型越复杂容易过拟合K值越大模型越平滑容易欠拟合。距离度量上常用欧氏距离和曼哈顿距离如果特征尺度差异大还需要标准化。热词里提到KNN算法的应用能力包括哪三个方面其实就是分类、回归和密度估计。KNN做回归时取K近邻的均值作为预测值做密度估计时样本密度可以用K近邻距离来衡量。KL散度这个概念对于2018年的实习生笔试有点超纲但它确实出现过主要是在变分推断或者EM算法的背景下。KL散度定义是D_KL(P||Q) Σ P(x) log(P(x)/Q(x))它衡量两个概率分布的差异。关键性质是非负且等于0当且仅当两个分布相同。但它不是对称的也就是D_KL(P||Q)不等于D_KL(Q||P)所以不是距离度量。如果题目提到KL散度与ELBO的关系那就要知道在变分推断里最大化ELBO等价于最小化真实后验与近似后验之间的KL散度。这个理论在推公式时很常见理解一次以后所有和VI相关的题都能秒杀。3.2 损失函数、正则化与偏差方差权衡这一块几乎是每张算法笔试必考的。最常见的题是L1正则化和L2正则化的区别是什么为什么L1更稀疏。答案是L1约束的解通常出现在坐标轴上因为它对应的优化区域是菱形极值点更可能落在某个参数为0的角点L2是圆形极值点一般不在坐标轴上所以参数不会变得恰好为0。如果从贝叶斯视角解释L1对应拉普拉斯先验L2对应高斯先验这个在陶哲轩的博客里写过面试时可以拿出来加分。偏差方差权衡也是常客。高偏差意味着模型欠拟合高方差意味着过拟合。题目往往会给出一个训练集误差和验证集误差的对比让你判断当前模型处于哪个状态。比如训练误差很低、验证误差很高明显是高方差解决办法是加正则化、增加数据、做早停或者降低模型复杂度。训练误差和验证误差都很高则是高偏差要增大模型容量、加特征、减少正则化。损失函数方面交叉熵和均方误差的选择是高频考点。分类问题用交叉熵回归问题用均方误差。面试喜欢追问为什么不用MSE训练分类模型因为MSE配合Sigmoid的输出会导致梯度消失而交叉熵的梯度形式里包含预测误差收敛更快。这个点每一年都有大量人栽跟头因为它需要你把损失函数求导推到一半才能看清。建议自己手推一遍二分类交叉熵对输出z的导数你会发现结果是(预测值-真实值)特别简洁。3.3 决策树、SVM和聚类算法的进阶细节决策树的考点集中在信息增益、信息增益比和基尼指数。ID3用信息增益选特征C4.5用信息增益比CART用基尼指数。客观题会给你一个小表格让你计算某个特征的信息增益然后选择分裂特征。这类题计算量不大但你必须记住对数的底数和公式里各项的系数。如果你用ln还是log2算反可能不影响排序结果但遇到两个特征信息增益接近时就很容易把答案算错。建议统一用log2把公式写在草稿纸最上面。SVM的考察思路通常是支持向量是什么、间隔最大化的含义、核函数的选择。最基础的题是问SVM的损失函数形式或者问线性不可分时怎么办。这里的关键是理解核函数的作用是隐式地把数据映射到高维空间而不显式计算映射。高斯核RBF可以把数据映射到无穷维但要注意Gamma参数过大会导致过拟合。如果你在客观题里看到某核函数对应无穷维特征空间的选项几乎肯定是在说RBF。聚类算法这块K-Means是必考。K-Means的步骤、收敛条件、初始K值敏感性都是选择题素材。我见过一道题问K-Means的初始点选择对结果的影响答案要点不好的初始簇中心可能导致局部最优解。因此出现了K-Means这种优化的初始化方法。如果题目问你如何选择聚类的K值常用的有肘部法则和轮廓系数。还需要知道K-Means对异常值敏感因为它用均值作为簇中心如果数据里有极端值可以用K-Medoids替代。4. 深度学习与工程算法考的是工程直觉深度学习在2018年的实习生笔试里比重还不算大但足够区分有没有真正做过实验的人。工程算法就更杂了从PID到BM25从卡尔曼滤波到模拟退火考的是一种算法工程师的广度。这一部分我单独拿出来讲因为它的备考方式和前面不同靠的是日常积累和项目经验。4.1 深度学习基础激活函数、正则化和优化器激活函数的考察是选择题标配。常见说法ReLU解决了Sigmoid在深层网络里的梯度消失问题计算也比Sigmoid快但它有个缺陷叫神经元死亡即输入负数时梯度恒为0参数无法更新。Leaky ReLU和PReLU就是为了改善这一点。Swish激活函数是Google在2017年提出的公式是x·sigmoid(x)在很多任务上优于ReLU。如果题目里出现2017年后提出的新激活函数大概率是Swish。池化层的作用出题人一定会问。最大池化的作用是保留最显著的特征并增加平移不变性平均池化则更平滑。它的另一个贡献是降低特征维度从而减少后续全连接层的参数量在一定程度上抑制过拟合。如果你在项目中用过卷积网络这些回答起来很自然如果只背过定义很容易漏掉平移不变性这一层。优化器这块题目会问SGD、Momentum、RMSProp、Adam的区别。核心是SGD沿梯度方向更新Momentum累加历史梯度来加速收敛并抑制震荡RMSProp对每个参数自适应调整学习率Adam则是Momentum和RMSProp的组合。有个记忆技巧凡是在实际训练中遇到过loss震荡的人都会理解Momentum带来的平滑效果。没实际训练过模型只能死记这些名字题目一换说法就懵所以建议至少去用PyTorch跑一次简单的图像分类把SGD和Adam各试一遍比背十遍都有效。4.2 非深度学习算法的工程场景PID、卡尔曼滤波和模拟退火这一块是小米的特色。因为它做硬件所以控制算法、滤波算法都进了考题。PID算法全称是比例-积分-微分控制在CRPS电源中常用于电压或电流的闭环调节。比例项决定响应速度积分项消除稳态误差微分项抑制超调。客观题要是问增大比例系数会带来什么影响答案是响应变快但稳定性下降可能出现振荡。如果你把PID类比成开车踩油门比例项是根据当前距离误差踩油门积分项是把历史累积误差也补偿进去微分项是根据误差变化趋势提前刹车这样理解就不容易忘。卡尔曼滤波的考点在于它的适用场景和基本思想用状态预测和带噪声的观测来更新系统状态适合线性高斯系统。如果系统是非线性的就需要扩展卡尔曼滤波或者无迹卡尔曼滤波。题目可能会给一个场景比如无人机的位置估计传感器有噪声问应该用什么方法选卡尔曼滤波就对了。它和PID的区别是一个做状态估计、一个做反馈控制两个不要混。模拟退火算法考的是以一定概率接受更差的解从而跳出局部最优这一点。温度高时接受劣解的概率大随着温度降低概率逐渐变小。客观题会问模拟退火在什么条件下容易收敛到全局最优答案是温度下降足够慢。如果温度下降太快退火过程就退化成贪心算法容易困在局部最优。这个算法思想在组合优化、神经网络超参搜索、甚至集成学习里的随机搜索变体中都有应用值得花点时间理解。粒子群算法PSO在热词里也出现了。PSO的核心是每个粒子同时追踪个体历史最优和全局历史最优来更新速度与位置。它比遗传算法简单没有交叉和变异操作所以实现起来很快。但它对参数惯性权重、个体学习因子、社会学习因子比较敏感容易早熟。笔试如果考PSO大概率会问粒子群算法的速度更新公式里两个随机项的作用是什么一个是认知部分代表粒子对自身经验的记忆一个是社会部分代表粒子向群体学习的能力。BM25算法在搜索排序里经常出现。它是TF-IDF的一个进阶版本对词频做了非线性饱和处理并且引入了文档长度归一化。客观题会问你BM25相比TF-IDF的改进点在哪里核心是词频超过一定阈值后对权重的影响不再线性增长这更符合真实相关性判断。如果你在项目中做过检索或QA系统这些问题顺手就能答没做过的话理解了这个点就够应付选择题。4.3 图像与信号处理从Laplacian到音频重采样图像算法在实习生的题里不会太难但会考察你对算子的理解。比如拉普拉斯算子用于图像锐化本质是二阶微分算子它提取的是图像的边缘信息把边缘叠加回原图就能增强细节。和Sobel算子对比Sobel是一阶微分计算梯度幅值来检测边缘拉普拉斯对噪声更敏感所以通常要先高斯模糊再用。这个点如果以Sobel算子和Laplacian算子的区别的形式出现抓住一阶和二阶就能选对。音频重采样算法听起来偏冷但是对做音频或语音方向的人是必考。它的核心问题是采样率转换比如从44.1kHz转到48kHz。最简单的实现是插值但直接插值会导致镜像频率所以需要先做低通滤波。常见的高质量重采样算法包括基于多相滤波器和基于FFT的实现。如果你没用过有个简单的记忆方式重采样绝不能直接在时域上跳点采样那样会引入混叠失真。异常检测算法也是近年热点但2018年那会儿更多出现在考查机器学习基础的部分。工业异常检测常见的思路有基于重构误差的方法比如自编码器在正常样本上训练异常样本的重构误差会较大还有基于密度估计的方法比如孤立森林。客观题通常问以下哪种方法适合高维异常检测孤立森林往往是个正确答案因为它不需要计算距离矩阵适合高维数据。5. 这套题的实战策略与备考避坑指南光知道知识点还不够客观题在有限时间内做完本身也是一门技术。我把自己复习和实战踩过的坑整理一下这几条建议对任何公司的算法笔试都适用。5.1 做题顺序与时间分配一张笔试卷子通常40到60道题时间60到90分钟。我的建议是先做数据结构与算法题再做机器学习与深度学习题最后做工程算法和杂题。原因是数据结构题通常相对独立不需要太多上下文思考可以先拿到基础分机器学习题目偶尔涉及长题干需要读题放中间做工程算法题如果不会可能蒙都蒙不对放到最后不会就不会不浪费时间。解题时凡是有数字计算的题先看选项分布。如果选项里两个数离得很近说明需要精确计算如果选项之间差距很大可以估算。比如信息增益的计算通常会给你log2表格这种题必须动笔算别心算。5.2 常见失分点和高频陷阱第一个失分点是审题不清。比如KMP的next数组题干可能写的是按严蔚敏教材定义还是按前缀函数定义这是天壤之别。我见过有人答对了但选错了选项就是因为没看定义。凡是涉及按下标从0开始还是下标从1开始的题不管看起来多简单都先把边界条件画出来再说。第二个失分点是概念混淆。比如过拟合的解决方案和欠拟合的解决方案经常混在一起考。关键要记住过拟合是模型太复杂解决方案是增加数据、加正则化、降维、早停欠拟合是模型太简单解决方案是加特征、加深网络、减正则化。如果题目给了一堆方案让你选哪些能解决过拟合凡是提到增加训练数据和增加L2正则化的基本就是正确答案。第三个失分点是排序算法的稳定性。建议平时把所有常见排序算法的稳定性亲手推一遍不要背表格。比如你写一次归并排序观察相等元素移动的方向你会立刻明白它为什么是稳定的。写一次快排和堆排也会立刻明白它们为什么不稳定。理解了原理这类题永远不会忘。第四个失分点是深度学习优化器的选择场景。很多题会给出一个具体任务比如训练一个深层CNN发现loss震荡严重应该换用什么优化器。你要是背过答案可能选Adam但如果你真的跑过实验你会知道还可以选SGDMomentum或者降低学习率。这种题没有标准答案选最优的那个但这恰恰是客观题里最容易有争议的地方。应对方法是看清楚题目问的是应该还是不应该把明显错误的选项排除掉选择描述最符合常识的选项。5.3 限时模拟练习的方法复习阶段我不建议只刷LeetCode因为客观题和代码题考察的侧重点不一样。LeetCode考的是你写代码能不能跑通客观题考的是你理解得够不够深。我自己的经验是做三遍真题。第一遍不限时边做边翻书。这个过程是查漏补缺发现自己哪个知识点薄弱。第二遍限时模拟完全按照笔试的时间来中间不能翻书。这个过程是训练做题节奏。第三遍看错题把每道错题对应的知识点再梳理一遍最好自己讲给自己听能用大白话把原理说清楚才算真的会。如果你能把一道题讲给一个完全不懂算法的人听懂那你在这道题上的理解深度就足够了。另外有时间的话一定要动手复现几个经典算法。没必要全写但至少把KMP的next数组、堆排序的建堆过程、朴素贝叶斯的分类过程、决策树的一个分裂步骤在纸上演算一遍。很多客观题比的就是这个手算能力。我个人在实际操作中的体会是准备这类笔试最容易犯的错误是贪多。搜索引擎里搜算法大全反而让人什么都会一点什么都不精。一份真题卷子把里面涉及的每个知识点吃透比刷一百道网站上的随机题有效得多。小米2018春招实习这套题其实并不偏门它考察的内容至今仍然是算法岗的核心基础。你把它当一次学期末的闭卷考试来准备把每一个为什么在大脑里过一遍考场上的表现一定不会差。最后再分享一个小技巧做题的时候凡是遇到以下选项哪一个不正确这种反向提问我的习惯是把每个选项都当判断题处理在草稿纸上给每个选项标上对或错然后再选。这样能避免被出题人的障眼法带偏。希望这份复盘能帮你顺利通过下一场笔试。