蘑菇街算法笔试题全解析：从KMP到贝叶斯的高频考点精讲

考过蘑菇街2019届校招算法笔试题的同学，应该都还记得那套题目的手感：选择题覆盖面很广，从KMP的next数组到贝叶斯公式，从堆排序到XGBoost特性，几乎把算法岗笔试能考的高频知识点都扫了一遍。这篇文章不是简单地把题目贴出来对答案，而是以这套笔试题为线索，把每一类考点背后的原理、答题思路、容易踩的坑都拆开讲清楚。

不管你是正在准备校招的应届生，还是想查漏补缺的社招选手，这篇内容都能帮你建立一个更清晰的算法笔试复习框架。我会把题目按知识点重新归类，补充推导过程、代码实现和备考建议，尽量还原我当年拆解这套题时的完整思考路径。

1. 考前摸底：笔试形式与真题结构复盘

1.1 题量与时间分配

蘑菇街算法类笔试，从我了解到的考生反馈来看，整体分三块：选择题、简答题、编程题。选择题大概在20道左右，覆盖数据结构、算法、机器学习、概率统计；简答题一般是2到3道，偏向模型原理或场景设计；编程题通常2道，一道偏基础数据结构，一道偏动态规划或贪心。

时间上一般是90到120分钟。看上去时间不算紧张，但实际做起来，选择题里隐含的计算量不小，尤其是概率题和机器学习推导题，单纯靠“感觉”选答案很容易翻车。我的经验是：选择题控制在40分钟内，简答题30分钟，剩下时间全部留给编程题。如果选择题卡壳超过3分钟，先标记跳过，别在一道题上耗到心态崩溃。

1.2 从真题看考点分布逻辑

蘑菇街做的是电商业务，算法岗位的技术栈侧重搜索、推荐、用户增长、风控这些方向。所以笔试里机器学习相关题目占比很高，而且喜欢把模型知识点和业务场景结合起来考。比如给你一个用户点击序列，问你怎么构造特征、选什么模型、怎么评估效果。

从考点表格能看出来，这套题并不追求冷门刁钻，而是把算法工程师日常最常用的知识体系完整地过一遍。数据结构和算法部分不会超出《剑指Offer》和LeetCode Hot 100的范畴，机器学习部分则明显偏向工程落地，而不是学术推导。

2. 数据结构与基础算法：笔试送分题与陷阱题拆解

2.1 KMP的next数组：一道题暴露字符串功底

这套笔试题里有一道非常经典的KMP题：对于模式串p="abacaba"，求其next数组，其中next[i]定义为模式串前i个字符组成的子串的最长相等前后缀长度。

这类题考察的不是你能不能默写KMP代码，而是你到底理解不理解next数组是怎么算出来的。网上很多教程把next数组的两种定义混在一起讲，导致很多人记了一堆模板还是不会算。

先明确一种常用定义：next[i]表示p[0...i-1]这个长度为i的前缀子串中，最长相等前后缀的长度。注意，这里的前缀和后缀都不能取整个子串本身。也就是说，next[i]是p[0...i-1]的最长公共前后缀长度（真前缀和真后缀）。

对p="abacaba"逐项计算：

• 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)，m=100。

堆排序还有一个容易考的点：建堆的时间复杂度。很多人以为是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附近是常数，参数更新时更容易跨过0；L2的梯度在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(X+Y)=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^13，13的二进制是1101，也就是a^13 = a^(8+4+1) = 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]表示长度为i+1的上升子序列中，末尾元素的最小值。遍历原数组时，用二分查找找到第一个不小于当前元素的位置，替换掉它。这样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 关于回忆版真题的打开方式

我写这篇文章，并不是鼓励大家去背“原题”。实际上，校招笔试题库每年都会更新，死记硬背原题意义不大。更有价值的做法是：通过回忆版题目，判断这家公司出题的侧重方向、难度层级、题型风格，然后针对性地调整自己的复习计划。

以蘑菇街这套笔试为例，它能告诉你的信息是：机器学习基础很重要、数据结构算法不能丢、概率统计要重点突破、编程题偏应用不偏竞赛。这几个方向往深了学，无论投哪家电商公司都用得上。把一套真题当成一面镜子，照出自己的薄弱点，比刷十套题都有价值。

最后再分享一个小技巧：如果你在笔试时遇到一道很熟悉但一时想不起完整做法的题，不要慌着硬编。先在草稿纸上把思路用中文写出来，再一步步翻译成代码。很多时候，思路理清了，代码自然就出来了。反而是一上来就敲代码，容易写到一半卡壳，心态一崩，后续题目全受影响。