考过蘑菇街2019届校招算法笔试题的同学应该都还记得那套题目的手感选择题覆盖面很广从KMP的next数组到贝叶斯公式从堆排序到XGBoost特性几乎把算法岗笔试能考的高频知识点都扫了一遍。这篇文章不是简单地把题目贴出来对答案而是以这套笔试题为线索把每一类考点背后的原理、答题思路、容易踩的坑都拆开讲清楚。不管你是正在准备校招的应届生还是想查漏补缺的社招选手这篇内容都能帮你建立一个更清晰的算法笔试复习框架。我会把题目按知识点重新归类补充推导过程、代码实现和备考建议尽量还原我当年拆解这套题时的完整思考路径。1. 考前摸底笔试形式与真题结构复盘1.1 题量与时间分配蘑菇街算法类笔试从我了解到的考生反馈来看整体分三块选择题、简答题、编程题。选择题大概在20道左右覆盖数据结构、算法、机器学习、概率统计简答题一般是2到3道偏向模型原理或场景设计编程题通常2道一道偏基础数据结构一道偏动态规划或贪心。时间上一般是90到120分钟。看上去时间不算紧张但实际做起来选择题里隐含的计算量不小尤其是概率题和机器学习推导题单纯靠“感觉”选答案很容易翻车。我的经验是选择题控制在40分钟内简答题30分钟剩下时间全部留给编程题。如果选择题卡壳超过3分钟先标记跳过别在一道题上耗到心态崩溃。1.2 从真题看考点分布逻辑蘑菇街做的是电商业务算法岗位的技术栈侧重搜索、推荐、用户增长、风控这些方向。所以笔试里机器学习相关题目占比很高而且喜欢把模型知识点和业务场景结合起来考。比如给你一个用户点击序列问你怎么构造特征、选什么模型、怎么评估效果。从考点表格能看出来这套题并不追求冷门刁钻而是把算法工程师日常最常用的知识体系完整地过一遍。数据结构和算法部分不会超出《剑指Offer》和LeetCode Hot 100的范畴机器学习部分则明显偏向工程落地而不是学术推导。知识模块典型考点题量预估难度数据结构与算法KMP、堆排序、二分、DP8-10题中机器学习基础逻辑回归、SVM、树模型5-6题中深度学习CNN、LSTM、过拟合3-4题中概率统计贝叶斯、期望、方差3-4题中高编程题字符串/数组处理、DP2题高2. 数据结构与基础算法笔试送分题与陷阱题拆解2.1 KMP的next数组一道题暴露字符串功底这套笔试题里有一道非常经典的KMP题对于模式串pabacaba求其next数组其中next[i]定义为模式串前i个字符组成的子串的最长相等前后缀长度。这类题考察的不是你能不能默写KMP代码而是你到底理解不理解next数组是怎么算出来的。网上很多教程把next数组的两种定义混在一起讲导致很多人记了一堆模板还是不会算。先明确一种常用定义next[i]表示p[0...i-1]这个长度为i的前缀子串中最长相等前后缀的长度。注意这里的前缀和后缀都不能取整个子串本身。也就是说next[i]是p[0...i-1]的最长公共前后缀长度真前缀和真后缀。对pabacaba逐项计算next[0]习惯上置为-1或0具体看题目定义。这里按长度为0处理记为-1很多教材用-1做失配跳转。next[1]子串a最长相等前后缀长度为0所以next[1]0。next[2]子串ab前缀有a后缀有b不相等长度为0。next[3]子串aba前缀a和后缀a相等长度为1前缀ab和后缀ba不相等所以next[3]1。next[4]子串abac前缀a和后缀c不相等长度为0。next[5]子串abaca前缀a和后缀a相等长度为1前缀ab和后缀ca不等前缀aba和后缀aca不等所以next[5]1。next[6]子串abacab前缀ab和后缀ab相等长度为2前缀aba和后缀cab不等所以next[6]2。next[7]子串abacaba前缀aba和后缀aba相等长度为3前缀abac和后缀caba不等所以next[7]3。所以按这个定义next数组为[-1, 0, 0, 1, 0, 1, 2, 3]。这里有个实战经验笔试里如果遇到next数组题先看清题目给的定义是“最长相等前后缀长度”还是“失配时跳转的位置”。有些题目会把next值整体减一或加一造成答案差异。我当年就吃过这个亏题目给的公式稍微改了改我没仔细看套了记忆中的模板白丢一道题。注意不同教材对next数组的下标起点和初始值定义不同。做题第一步永远是确认定义而不是直接套模板。2.2 排序与堆不只是背复杂度笔试里排序算法几乎必考但考察形式很灵活。比如给你一个几乎有序的数组问用什么排序最快。这题考察的不是复杂度背诵而是理解排序算法的实际表现。插入排序在数组基本有序的情况下时间复杂度可以降到O(n)。所以“几乎有序的数组”最优解一般是插入排序而不是快速排序或归并排序。还有一道典型题从10亿个数中找出最大的100个数用什么数据结构标准答案是最小堆堆大小为100遍历数据时如果当前元素大于堆顶就替换堆顶并调整堆。时间复杂度O(n log m)m100。堆排序还有一个容易考的点建堆的时间复杂度。很多人以为是O(n log n)记住了答案不知道为什么。实际上对长度为n的数组从最后一个非叶子节点开始下沉每个节点的下沉代价和它的高度成正比总代价求和是O(n)。我第一次推导这个结论时还不太相信后来手算了几个例子发现确实如此。这属于“光背结论不推过程”就会漏掉的考点。2.3 贪心、二分、图算法典型题路线这套笔试的选择题里贪心和二分的题目比较常规。贪心那边经典的是区间调度问题给你一堆会议时间问最多能参加多少个。思路是每次选结束时间最早的会议然后跳过冲突的继续选下一个结束时间最早的。这就是很典型的贪心策略证明过程其实是用“交换论证法”说明最优解里第一个会议一定可以换成结束时间最早的会议而不影响可行性。二分那边题目一般会考察二分查找的边界条件比如while (left right)还是while (left right)mid到底是取左中位数还是右中位数。这些细节在笔试里不是让你写代码而是直接判断某段代码会不会死循环。我的建议是平时把二分的几种写法都固定下来不要今天写一种明天换一种。图算法这块Dijkstra、拓扑排序、并查集都算高频。Dijkstra容易被问到的一个点是为什么不能处理负权边因为Dijkstra基于“当前距离最小的节点不会再被更新”的贪心假设一旦出现负权边这个假设就不成立了。还有一道经典题如何判断一个有向图里是否存在环拓扑排序统计每个节点的入度入度为0的节点入队不断弹出并减少邻居的入度如果最后弹出的节点数不等于总节点数说明存在环。这个方法在工程里也很常用比如做依赖解析时判断循环依赖。3. 机器学习与深度学习理论题怎么答才不丢分3.1 线性模型与正则化穿插场景题蘑菇街笔试里逻辑回归是必考项。比如问逻辑回归的损失函数为什么用交叉熵而不用均方误差。因为逻辑回归的预测值经过sigmoid函数后是非线性的如果用均方误差损失函数关于参数不是凸函数梯度下降容易陷入局部最优而交叉熵损失函数关于参数是凸的收敛更稳定。还有一个高频点L1正则和L2正则的区别。L1正则会把参数往0方向压缩产生稀疏解可以用于特征选择L2正则只会让参数变小但不会变成0能防止过拟合。为什么会有这个区别因为L1的梯度在0附近是常数参数更新时更容易跨过0L2的梯度在0附近趋近于0参数很难精确到达0。简答题里可能会让你设计一个回归模型预测用户未来30天的购买金额。这时候要注意不要把模型选型写死而应该先分析数据特点用户购买金额通常符合长尾分布很多用户不购买所以可以考虑两阶段建模先做二分类预测“是否购买”再对预测会购买的用户做金额回归。这种回答能体现出你对业务场景的理解比单纯写公式得分更高。3.2 树模型与集成学习GBDT和XGBoost高频考点树模型相关题目在电商类算法笔试里占了很大比重。有一道经典题随机森林和GBDT的区别是什么可以从几个维度回答随机森林是Bagging思路各棵树独立训练最后投票或取平均GBDT是Boosting思路每棵树拟合前一棵树的负梯度残差近似是串行训练。随机森林能降低方差GBDT能降低偏差。随机森林对异常值更鲁棒GBDT对异常值敏感。XGBoost也是常客。它相对于GBDT的改进点一般要答出目标函数里加了正则项对叶子节点数和叶子权重做惩罚对损失函数做了二阶泰勒展开比一阶信息更精确支持列抽样不仅能减少过拟合还能加速训练能自动处理缺失值。这些点知道不难难的是用通顺的语言组织成一道简答题的答案。我的建议是平时就整理出一份“面试背诵版”把这类高频简答题的答案提前写好笔试时直接复用。3.3 深度模型与NLP/CV基础深度学习的选择题相对基础但也不能掉以轻心。比如问CNN中感受野的计算方式或者问LSTM能解决RNN的什么问题。LSTM那道题标准答案是“缓解梯度消失问题”但要注意措辞LSTM通过门控机制让梯度在时间维度上有一条“高速公路”所以能缓解梯度消失但并不能完全解决梯度爆炸梯度爆炸还是要靠梯度裁剪。NLP基础题可能会考Word2Vec的两种模型CBOW和Skip-gram。CBOW用上下文预测中心词Skip-gram用中心词预测上下文。对生僻词Skip-gram效果通常更好因为它对每个词都做了更多次更新对高频词CBOW的收敛速度更快。这道题在推荐系统场景里还经常被延伸一下能不能用Item2Vec做物品向量本质就是把用户的行为序列当成“句子”物品当成“词”用Word2Vec的思路训练。3.4 评价指标与过拟合这部分的题一般不会直接问“什么是AUC”而是给你一个场景让你选合适的评估指标。比如正负样本极度不平衡的点击率预测任务用准确率评估会有什么问题准确率会被多数类主导一个全预测为负类的模型也能有很高的准确率但实际上没有任何用处。这时应该看AUC、召回率、F1分数等指标。过拟合的题目高频问法包括什么是过拟合、如何检测过拟合、如何缓解过拟合。缓解手段一定要答全面不能只说正则化数据层面可以增加数据量、做数据增强模型层面可以降低模型复杂度、加dropout、加L1/L2正则训练层面可以早停、交叉验证。还有一点容易被忽略过拟合的特征是训练集损失低、验证集损失高如果训练集和验证集损失都很高那是欠拟合处理方法完全不同。很多同学把这两者搞混简答题写了一大段但方向错了非常可惜。4. 概率统计与数学容易被忽视的拉分项4.1 贝叶斯公式笔试常青树贝叶斯公式基本是必考。有一道经典题目某疾病在人群中的患病率为0.1%检测方法的准确率为99%即患病者检测阳性的概率为99%未患病者检测阴性的概率为99%。如果一个人检测结果为阳性他真正患病的概率是多少设事件A为患病事件B为检测阳性。根据贝叶斯公式P(A|B) P(B|A) * P(A) / P(B)其中P(B) P(B|A) * P(A) P(B|¬A) * P(¬A) 0.99 * 0.001 0.01 * 0.999。代进去算结果大概只有9%左右。这个结论非常反直觉但计算过程就是套公式。这道题在笔试里出现的概率很高因为考察了三件事一是贝叶斯公式的掌握程度二是全概率公式的运用三是对先验概率重要性的理解。很多同学算出9%后都不敢选觉得检测准确率都99%了患病概率怎么着也得过半吧。这就是没有真正理解贝叶斯思想——先验概率极低时即使证据很强后验概率也不会太高。提示做贝叶斯公式的题第一步是清晰写出事件定义第二步是写全概率公式展开分母第三步才是代入数值。跳过第二步直接代数字很容易算错。4.2 期望、方差与排列组合概率统计的选择题有时会考期望的线性性质E(XY)E(X)E(Y)不需要X和Y独立。这个性质看着简单但考法很灵活。比如把n个球随机放入n个盒子每个盒子可以放多个球问空盒子数量的期望。这个题如果一个个分析空盒子数量的分布就麻烦了但用期望线性性质可以直接算对每个盒子定义指示变量等于1表示该盒子为空空盒子总数就是这些指示变量的和。每个盒子为空的概率是(1-1/n)^n所以空盒子期望数量就是n乘以(1-1/n)^n。这个思路很巧妙也很符合算法工程师的思维习惯。排列组合常见的是古典概型问题比如“一副扑克牌抽5张至少有一张A的概率”。这种题要注意直接算“至少”很麻烦要反过来算“一张A都没有”的概率然后1减去这个概率。就是典型的“正难则反”思想。4.3 快速幂与数值计算热词里有“快速幂算法c”这其实也是笔试里常见的一道技巧题。快速幂的核心思想是把指数二进制分解比如计算a^1313的二进制是1101也就是a^13 a^(841) a^8 * a^4 * a^1。只需要4次乘法就搞定而不是13次。代码实现很简洁核心就是循环里判断当前二进制位是否为1以及底数不断平方def quick_pow(a, b, mod): res 1 while b 0: if b 1: res res * a % mod a a * a % mod b 1 return res这道题在数学类题目里属于“会了就觉得简单不会就硬算”的类型。我备考时专门把这几种常考小技巧整理过快速幂、辗转相除法求最大公约数、埃氏筛/欧拉筛求素数。笔试不一定直接考但这些底层数学工具在很多题目里都会用到。5. 编程题实战两道经典题的完整解题思路5.1 最长上升子序列LIS编程题第一道回忆版里很接近LeetCode的“最长上升子序列”问题给定一个无序数组求最长严格递增子序列的长度。比如[10, 9, 2, 5, 3, 7, 101, 18]答案是4[2, 3, 7, 101]。最基础的解法是动态规划定义dp[i]表示以第i个元素结尾的最长上升子序列长度。状态转移方程dp[i] max(dp[j] 1) # 对所有 j i 且 nums[j] nums[i]初始化dp数组全为1因为每个元素至少可以单独成为一个子序列。时间复杂度O(n^2)空间复杂度O(n)。这题还有一个优化版本用贪心二分把时间复杂度降到O(n log n)。核心思想是维护一个tails数组tails[i]表示长度为i1的上升子序列中末尾元素的最小值。遍历原数组时用二分查找找到第一个不小于当前元素的位置替换掉它。这样tails数组的长度就是最长上升子序列的长度。我当年笔试时直接写了O(n^2)的DP版本因为时间紧张没敢冒险写二分优化。如果你的编程基础扎实建议直接练熟二分优化版本因为面试官追问“能不能优化”时它能体现你的算法深度。5.2 零钱兑换与背包类问题另一道编程题偏向动态规划比如零钱兑换给定不同面额的硬币和一个总金额求凑成总金额所需的最少硬币个数。如果不可能凑成返回-1。这道题完全就是背包问题的变体。状态定义是dp[i]表示凑成金额i所需的最少硬币数。状态转移dp[i] min(dp[i - coin] 1) # 对每个 coin i初始化dp[0] 0其他金额初始化为无穷大。最终dp[amount]就是答案。这里有个容易踩的坑外层循环是金额还是硬币内层循环是正序还是倒序零钱兑换里每个硬币可以无限使用属于“完全背包”所以内层循环要从硬币面额正序遍历到总金额这样每个硬币可以被重复使用。如果是01背包内层循环就要倒序保证每个物品只用一次。这两个写法搞反了结果就会出问题。注意笔试编程题一定要先写清楚暴力/基础版本再考虑优化。哪怕最后没时间优化基础版本能通过部分测试用例也比空着不写强很多。6. 备赛节奏与避坑清单6.1 三轮复习时间线如果你已经决定冲刺这类含算法笔试的校招岗位我建议按三轮来准备。第一轮是知识梳理控制在1到2周。把数据结构数组、链表、栈、队列、树、图、哈希表、基础算法排序、二分、双指针、滑动窗口、递归、贪心、动态规划、机器学习基础线性模型、树模型、SVM、聚类、评价指标过一遍。不用每题都刷主要任务是建立知识框架。第二轮是题海实战建议3到4周。每天保持2到3道编程题的强度重点刷LeetCode Hot 100和《剑指Offer》。同时每周做一次整套笔试模拟题严格控制时间训练做题节奏。我自己的体会是模拟笔试一定要用纸笔或者在线笔试系统不能只在IDE里写。第三轮是查漏补缺考前一周左右。翻看之前错题重点复习容易混淆的知识点比如L1和L2正则的区别、GBDT和随机森林的区别、KMP中next数组的不同定义、二分的边界写法、动态规划的状态定义技巧。简答题提前整理好背诵版答案考场上直接输出。6.2 高频失分点自查清单我整理了一份高频失分点清单每次模拟考完都对着看一遍选择题没注意题目对next数组的定义直接套模板。概率题算贝叶斯公式时分母的展开漏了“未患病但检测阳性”这一项。机器学习选择题把“降低方差”和“降低偏差”搞反。编程题没看数据范围直接用O(n^2)解法导致超时。编程题忘了处理边界条件比如输入为空数组、目标金额为0。简答题只写结论不写理由比如只写“用L1正则”不解释“为什么”。时间分配失衡选择题花太多时间导致编程题没写完。这7条基本覆盖了大多数人在校招笔试里踩过的坑。每次模拟考后对照自查能明显减少重复犯错。6.3 关于回忆版真题的打开方式我写这篇文章并不是鼓励大家去背“原题”。实际上校招笔试题库每年都会更新死记硬背原题意义不大。更有价值的做法是通过回忆版题目判断这家公司出题的侧重方向、难度层级、题型风格然后针对性地调整自己的复习计划。以蘑菇街这套笔试为例它能告诉你的信息是机器学习基础很重要、数据结构算法不能丢、概率统计要重点突破、编程题偏应用不偏竞赛。这几个方向往深了学无论投哪家电商公司都用得上。把一套真题当成一面镜子照出自己的薄弱点比刷十套题都有价值。最后再分享一个小技巧如果你在笔试时遇到一道很熟悉但一时想不起完整做法的题不要慌着硬编。先在草稿纸上把思路用中文写出来再一步步翻译成代码。很多时候思路理清了代码自然就出来了。反而是一上来就敲代码容易写到一半卡壳心态一崩后续题目全受影响。