蘑菇街2019届实习生算法工程师笔试考完复盘了一个多星期把记得的题目和踩过的坑都整理出来了。这份试题对于准备投电商类算法岗、尤其是实习岗位的同学来说参考价值很大——它基本代表了互联网公司算法实习生笔试的典型风格数据结构与算法是绝对主体机器学习/深度学习只占一小部分但每次都会出现一两道让你纠结半天的概率题。我这篇不打算逐题给标准答案而是把每道题背后的考点脉络、我当时的思考过程、以及对复习方向的引导完整拆开相信对正在准备笔试的同学会有实实在在的帮助。1. 笔试全景蘑菇街算法实习生到底考什么1.1 岗位定位与考察逻辑蘑菇街是电商平台算法工程师实习生主要面向搜索、推荐、广告、用户增长这些业务方向。这类岗位有一个共同特点数据结构基础必须过硬工程能力不能差同时需要懂机器学习的基础理论和常见模型。笔试题目会围绕这三个维度展开但权重很明显——数据结构与算法占了差不多六成机器学习和概率统计各占两成左右。我当时拿到的试卷结构和网上很多人回忆的基本一致先是几道选择题覆盖排序算法、字符串匹配、堆、图论然后是2-3道编程题难度递进第一道送分、第二道中等、第三道压轴最后是简答/论述题关于机器学习模型或概率推导。这里有个很重要的信息笔试只是第一轮筛选后面还有面试所以笔试既不能太简单否则起不到筛选作用也不会难得离谱不然通过率太低人力成本太高。我当时的策略是选择题保证正确率编程题前两道尽量AC第三道尽力写部分分简答题写清楚思路比堆砌公式更重要。1.2 各模块分值分布与时间分配建议根据考试整体反馈我整理了一个大致的模块分布表虽然每一届的题目会有调整但结构基本稳定。考试模块大致分值占比主要考点建议耗时数据结构与算法55%-65%排序、链表、字符串、树、图、动态规划60-75分钟机器学习基础15%-20%损失函数、过拟合、特征工程、常见模型15-20分钟概率统计10%-15%贝叶斯、期望、分布、参数估计10-15分钟简答/方案设计10%-15%推荐系统、AB实验、业务场景题15-20分钟如果你是第一次参加这类笔试我建议拿到卷子先把全部题目扫一遍心里有数之后再动手。编程题卡住超过20分钟就该先跳过把后面拿得准的分先保住这是所有算法笔试的通用打法。2. 数据结构与算法刷题核心区拆解2.1 KMP算法与next数组字符串匹配的必考题KMP算法是算法笔试的高频考点蘑菇街这份卷子里有一道非常经典的题考的是next数组的计算。原题描述大概是对于模式串 pabacaba求它的next数组其中next[i]定义为字符串前i个字符组成的子串中最长相同前后缀的长度。我当时看到这道题第一反应就是考的是定义理解和手算能力不是背代码。这类题目只要你真正理解了next数组的含义根本不需要去记什么“优化版nextval”老老实实按定义算就行。以abacaba为例我们手动推一遍next[1]子串a没有真前后缀为0next[2]子串ab最长相同前后缀为0next[2]0next[3]子串aba前缀a后缀a长度1next[3]1next[4]子串abac前缀a、ab、aba后缀c、ac、bac无匹配next[4]0next[5]子串abaca前缀aa后缀长度1但aba和后缀aca不匹配所以next[5]1next[6]子串abacab前缀ab后缀ab长度2next[6]2next[7]整个串abacaba最长相同前后缀是aba长度3next[7]3所以答案是[0, 0, 1, 0, 1, 2, 3]。这道题的关键是理解“前缀”和“后缀”都不能取整个字符串本身。很多同学这里记混把next[7]算成0那就是把“最长相同前后缀”理解成了“最长相同真前后缀”概念没吃透。关于KMP我多说两句。面试时除了手算next数组还经常让写KMP的匹配过程。核心代码如下我习惯用C写vectorint getNext(const string p) { int n p.size(); vectorint next(n 1, 0); for (int i 2, j 0; i n; i) { while (j p[i-1] ! p[j]) j next[j]; if (p[i-1] p[j]) j; next[i] j; } return next; } int kmp(const string s, const string p) { int n s.size(), m p.size(); if (m 0) return 0; vectorint next getNext(p); for (int i 0, j 0; i n; i) { while (j s[i] ! p[j]) j next[j]; if (s[i] p[j]) j; if (j m) return i - m 1; } return -1; }这里有个容易出错的地方next数组的下标从1开始还是从0开始不同教材定义不一样。我建议统一用“next[i]表示前i个字符的最长相同前后缀长度”这样在匹配时失配跳转更直观。2.2 排序算法与复杂度分析选择题常客选择题里必然有排序算法蘑菇街这类公司喜欢考的是某种排序算法在特定数据下的表现、稳定性、时间复杂度的最好/最坏情况。比如有一道题我印象很深问在数据基本有序的情况下以下哪个排序算法最快选项有冒泡、快排、堆排、归并。答案其实是冒泡排序。这个结论看起来反直觉但仔细分析一下数据基本有序时冒泡排序经过一轮扫描发现没有发生交换就可以提前结束时间复杂度退化为O(n)。而快排如果每次选的基准都是最值会退化成O(n²)。堆排序无论数据怎样都是O(n log n)归并排序也稳定在O(n log n)。同理快速排序在完全乱序时平均O(n log n)但在已经有序时如果固定取第一个元素作为pivot会退化到O(n²)。这是一个高频考点复习时一定要记住“快排怕有序”。我把各类排序算法的关键特性整理成了表笔试前建议反复看排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定稳定性这个点面试很喜欢追问。比如你给一个对象数组先按时间排序再按优先级排序如果要用稳定排序才能保证两次排序后时间维度依然有序这就引出了为什么系统排序函数像C的stable_sort用归并、而sort用快排插入的混合策略。2.3 链表、栈与队列不能丢的基础分笔试题里链表类的题目属于“送分但不能丢”的范畴。常见的有反转链表、判断链表是否有环、找链表中点、合并两个有序链表。这些题不复杂但要求你bug-free地写出来这考察的是对指针/引用的底层理解。反转链表我推荐迭代写法面试时写递归容易被追问栈溢出问题ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; }注意边界条件链表为空时返回空只有一个节点时返回该节点。多练几遍就不容易出错。关于栈和队列笔试更倾向于考察它们的应用场景比如用两个栈模拟队列、单调栈求下一个更大元素、滑动窗口最大值。“滑动窗口最大值”是一道好题它体现了“单调队列”的思想。维护一个双端队列保证队首永远是当前窗口的最大值。每次窗口右移时把小于新元素的队尾元素全部弹出再把队列中已不在窗口内的元素从队首弹出。vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; vectorint res; for (int i 0; i nums.size(); i) { if (!q.empty() q.front() i - k 1) q.pop_front(); while (!q.empty() nums[q.back()] nums[i]) q.pop_back(); q.push_back(i); if (i k - 1) res.push_back(nums[q.front()]); } return res; }2.4 堆排序与TopK问题互联网公司偏爱的考点TopK问题是我在蘑菇街笔试里见到的又一大类。常见问法从海量数据中找出最大的K个数。核心思路是用一个大小为K的最小堆堆顶是当前K个数中最小的遍历完所有数据之后堆里存的就是最大的K个。C里可以直接用优先队列vectorint topK(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; for (int x : nums) { pq.push(x); if (pq.size() k) pq.pop(); } vectorint res; while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); } return res; }用最小堆的时间复杂度是O(n log k)在海量数据场景下非常实用因为你并不需要一次性把所有数据加载进内存只需要维护一个大小为K的堆数据可以流式处理。这在大数据场景下是标准解法面试官很看重这个思路。2.5 图论与最短路径Dijkstra的变种题图论题目在实习笔试中一般不是最难的但Dijkstra算法作为最短路的基础算法考到的概率很高。蘑菇街这场考试有一道题给了一张带权无向图要求从源点到终点的最短路径同时要求“如果有多条最短路径输出经过节点最少的那条”这就是Dijkstra加一个二级约束的典型变种。处理方式也很直接在dist数组之外再维护一个cnt数组cnt[i]表示到节点i的最短路径需要的最少节点数。当通过u中转到达v的距离更短时同时更新dist[v]和cnt[v]cnt[u]1当距离相等但节点数更少时只更新cnt[v]。void dijkstra(vectorvectorpairint, int graph, int s, int t) { int n graph.size(); vectorint dist(n, INT_MAX), cnt(n, INT_MAX); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[s] 0; cnt[s] 1; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; cnt[v] cnt[u] 1; pq.push({dist[v], v}); } else if (dist[v] dist[u] w cnt[v] cnt[u] 1) { cnt[v] cnt[u] 1; } } } cout dist[t] cnt[t] endl; }这类“最短路径 额外条件”的题目在笔试中很常见核心是理解Dijkstra的松弛操作然后在此基础上扩展状态。记住一点Dijkstra的优先队列中可能出现同一个节点的不同距离版本所以出队时要判断d dist[u]就跳过。2.6 快速幂看似简单但容易翻车代码题里有一道很经典的快速幂题目计算a的b次方对m取模a和b都可能很大比如10^18级别。没有接触过快速幂的同学第一反应是循环相乘但这在b很大时肯定超时。快速幂的核心思想是二进制拆分b可以表示为二进制每一位的权值是a的2^k次方累乘得到a^b。long long fastPow(long long a, long long b, long long m) { long long res 1 % m; a % m; while (b 0) { if (b 1) res res * a % m; a a * a % m; b 1; } return res; }这里有几个坑需要注意a要先对m取模防止溢出res初始化要写成1 % m因为m可能等于1乘法结果记得每一步都取模。2.7 动态规划与贪心压轴题的常客蘑菇街笔试压轴编程题大概率是动态规划我那年考了一道带条件的背包问题。这种题的特点是看起来像背包但不完全是常规的0-1背包或完全背包而是加了一些业务约束。遇到动态规划题目我建议按这样的顺序思考明确状态设计dp[i][j]代表什么写出状态转移方程确定初始化条件和边界优化空间复杂度通常可以从二维压到一维背包问题的典型状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])倒序遍历j是为了保证每个物品只取一次这是0-1背包区别于完全背包的关键。贪心算法在笔试中更多以选择题或简答题的形式出现比如活动安排问题、哈夫曼编码、找零钱问题在某些货币体系下贪心不一定最优。考贪心时要注意能证明贪心策略的正确性比能写出代码更重要面试官很爱追问“为什么贪心是对的”。3. 机器学习与深度学习基础电商算法岗的硬门槛3.1 损失函数与模型评估蘑菇街作为电商平台算法工程师日常要面对的是点击率预估、转化率预估、商品排序、用户画像等任务。笔试题目会围绕这些业务场景考察机器学习基础而不是空泛地问“什么是过拟合”。比如有一道选择题问的是在CTR预估中如果正负样本比例严重不平衡以下哪个评估指标最不合适选项里有accuracy、precision、recall、AUC。答案是accuracy。原因是正负样本比例100:1时模型全部预测为负样本accuracy也能到99%但这个模型毫无意义。AUC对样本不平衡相对不敏感是CTR预估场景最常用的离线评估指标。这里把几个核心概念做一个对照概念含义使用场景accuracy预测正确的样本占总样本比例各类别均衡时precision预测为正的样本中真正为正的比例误报成本高时recall真正的正样本中被预测出来的比例漏报成本高时F1precision和recall的调和平均需要兼顾两者时AUCROC曲线下面积排序能力、样本不平衡时实际笔试中经常考到F1的公式F1 2 * precision * recall / (precision recall)。3.2 逻辑回归与损失函数推导逻辑回归是电商算法岗笔试的必考模型原因很简单它在工业界用得太多了CTR预估的baseline就是LR特征工程。逻辑回归的损失函数是交叉熵损失L(w) -1/N * Σ [y_i * log(h(x_i)) (1-y_i) * log(1-h(x_i))]为什么要用交叉熵而不是均方误差因为逻辑回归的预测值经过sigmoid函数映射到(0,1)区间使用均方误差会导致损失函数非凸优化过程容易陷入局部最优。交叉熵配合sigmoid损失函数是凸函数梯度下降可以收敛到全局最优。我当时在简答题里还写了梯度推导过程对sigmoid函数求导得到σ(z) σ(z)(1-σ(z))然后代入交叉熵的梯度公式最终得到梯度表达式是X^T (h(X) - y) / N形式和线性回归的梯度一致这个结论很优美也说明逻辑回归本质上是一个线性模型加了一个非线性变换。3.3 过拟合与正则化面试官最爱的追问点过拟合是笔试里出现频率最高的概念之一。问法通常是模型在训练集上表现很好但测试集上很差可能是什么原因怎么解决标准回答思路是原因模型复杂度过高、训练数据不足、特征太多、训练轮次过多解决方法增加训练数据、降低模型复杂度、正则化L1/L2、Dropout、早停、交叉验证关于L1和L2正则化的区别这里多说一句L1正则化倾向于让部分特征的权重变为0起到特征选择的作用L2正则化倾向于让所有特征的权重都变小但不会变成0。原因从梯度更新角度看L1的梯度是常数每次更新都会让权重向0方向移动固定步长L2的梯度是权重的线性函数当权重接近0时梯度也趋近0所以不会真正变成0。3.4 推荐系统基础蘑菇街业务场景的核心电商算法岗笔试对推荐系统的考察一般是概念级别比如推荐系统的常见召回策略和排序策略。召回阶段关注的是从海量物品中快速找到候选集常见方法有协同过滤基于用户/基于物品、向量召回双塔模型、规则召回热门、新品、类目等。排序阶段则是用CTR/CVR模型对候选集精排常见模型从LR、GBDT到DeepFM、DIN等。如果笔试中出现“如何设计一个推荐系统”这类开放题我建议按“召回-粗排-精排-重排”这个链路来答每一层说明目标和一个常用方法。不用写太深但要让面试官看到你有完整的体系认知。3.5 强化学习与其他模型拓展视野的加分项近年来很多互联网公司的笔试会把强化学习、对抗生成网络等内容作为选择题或简答题放进试卷里考察面比较广。比如在线广告竞价中的竞价策略、动态定价等问题本质上都可以用强化学习的框架去建模。这里提一下相关热搜词里出现的粒子群算法和模拟退火算法。这些属于元启发式优化算法在特征选择、超参数调优、神经网络权重初始化等场景下会有应用。虽然笔试直接考算法细节的概率不高但如果你在简历里写了相关项目面试官可能会追问。我建议至少理解粒子群算法的核心思想一群粒子在搜索空间中移动每个粒子记住自己的历史最优位置pbest并共享群体最优位置gbest速度更新公式是v_i w * v_i c1 * r1 * (pbest_i - x_i) c2 * r2 * (gbest - x_i)w是惯性权重c1和c2是学习因子r1和r2是[0,1]随机数。理解这个公式的关键是粒子的下一步移动既保留了自己的运动惯性又受到个人经验和群体经验的双重牵引。4. 概率统计与综合题拉开差距的关键4.1 贝叶斯公式与条件概率概率统计在笔试中占比不大但每年必考而且往往能拉开差距。因为数据结构和算法题目通过大量刷题能快速提升但概率题考察的是数学功底临时抱佛脚效果有限。贝叶斯公式是最高频的考点P(A|B) P(B|A) * P(A) / P(B)我遇到的题目是某商品被点击的概率是0.1被点击后购买的概率是0.5未被点击时购买的概率是0.05。求“已知用户购买了该商品他之前点击过该商品的概率”。设A表示点击B表示购买。P(A)0.1P(B|A)0.5P(B|A)0.05。先算P(B)P(B|A)P(A)P(B|A)P(A)0.50.10.050.90.050.0450.095。然后P(A|B)0.5*0.1/0.095≈0.526。这道题的关键是不要漏掉“未点击但购买”的概率分支很多同学只算分子忘了算分母。4.2 期望与随机变量常见的期望递推题期望是另一个高频考点尤其是“摸球问题”、“掷骰子问题”这类经典模型。有一种题型是从1到n随机选一个整数期望值是多少那答案就是(n1)/2如果随机变量均匀分布期望就是均值。有时候会考一个递推期望掷一枚骰子直到出现6所需次数的期望。这个用几何分布可以直接算E1/p6。如果面试官问更复杂的版本比如“出现连续两个6才停”就需要用马尔可夫链和期望递推求解这属于进阶内容笔试考到的概率不高但如果你能答出来会是很好的加分项。4.3 方案设计题现场拆解业务问题蘑菇街笔试的简答题部分有一类方案设计题比如“如何预测用户未来7天的购买金额”或者“如何评估一个新推荐策略的上线效果”。这类题目没有标准答案但评分标准是有迹可循的考察你是否具备完整的机器学习建模思路。我总结了一套通用的答题框架目标定义是回归问题还是分类问题评估指标是什么数据收集需要哪些特征用户历史行为、商品属性、时间特征等特征工程怎么做特征交叉、怎么做归一化、怎么处理缺失值模型选择Baseline选什么进阶用什么评估方法离线评估用什么指标线上怎么设计AB实验上线与监控灰度发布、线上效果监控、回滚机制按这个框架展开来写至少能拿一半以上的分数。比较忌讳的是只回答“用机器学习模型”没有任何细节支撑这会让面试官怀疑你的工程落地能力。4.4 海量数据与大数据处理技巧电商公司最不缺的就是数据所以笔试里也可能出现海量数据处理的问题比如“有100亿个整数如何在其中找到出现次数最多的Top100”。这种题考察的是分治思想和外部排序能力。经典解法是哈希分片把100亿个数通过hash函数映射到1000个小文件中每个文件大约1000万个数内存可以放下。然后对每个小文件统计出现次数并取Top100最后再对所有小文件的Top100做一次归并得到全局Top100。另外一个常见考点是“如何在两个大文件中找出相同的URL”思路是用哈希分片把两个大文件分别拆分成小文件然后对相同编号的小文件做集合求交。这类题的核心就是“大文件化小内存放得下”。4.5 分类算法与聚类算法覆盖面要广笔试选择题中有时会出现“以下哪个算法属于无监督学习”这类题目考察你对算法分类的掌握。K-Means、DBSCAN、层次聚类属于无监督学习逻辑回归、决策树、SVM、随机森林、GBDT属于监督学习。这里顺手把几个相关热搜词里的算法做一个快速梳理方便你查漏补缺算法类别典型应用KNN监督学习分类/回归推荐、图像分类K-Means无监督学习聚类用户分群Dijkstra图论算法最短路径快速幂数论算法大数幂运算、模运算模拟退火元启发式优化TSP、调度优化粒子群算法元启发式优化参数优化、特征选择BM25信息检索搜索排序卡尔曼滤波状态估计目标跟踪、导航如果你在笔试前时间充裕建议把KNN的三个核心应用场景分类、回归、推荐和K-Means的算法流程都过一遍尤其是K-Means的收敛条件和对初始中心点的敏感性面试追问概率很高。5. 常见问题与备考策略5.1 刷题误区与避坑指南我见过太多同学在准备算法笔试时陷入刷题误区最典型的有三种第一种是只看题解不自己动手写。感觉看懂了别人的思路但自己动手时连边界条件都写不对。我的建议是每道题至少自己独立写一遍然后隔一周再写一遍做到“三刷”。第二种是光刷LeetCode不总结。刷题不是数量竞赛一个月刷300题和一个月认真吃透80题从笔试结果来看后者往往更好。建议用表格整理每道题的核心思路、时间/空间复杂度、易错点形成自己的错题本。第三种是忽略基础直接攻难题。有些同学一上来就刷Hard题结果基础数据结构都写不利索。笔试的题目难度分布其实是60%的中等偏下题30%的中等题10%的难题。把中等偏下题的分都拿到笔试基本就稳了。5.2 时间规划45天实习笔试备考计划针对蘑菇街这类电商公司的算法实习笔试结合热搜词里高频出现的KMP、排序、贪心、动态规划、强化学习等算法我整理了一个45天的备考计划按“基础-强化-冲刺”三个阶段划分阶段时间重点任务基础阶段第1-15天数据结构系统复习数组、链表、栈、队列、哈希表、树、图每天2-3道基础题强化阶段第16-30天专项突破排序、二分、双指针、滑动窗口、KMP、Dijkstra、DP、TopK每天3-4道中等题冲刺阶段第31-45天刷真题/模拟题控制时间模拟真实笔试整理错题复习机器学习基础和概率统计基础阶段重点在“会写”强化阶段重点在“会优化”冲刺阶段重点在“会取舍”。实际笔试中时间管理往往比能力更关键。5.3 面试前技术栈自检清单笔试通过之后紧接着是面试有些内容笔试不考或者考得浅但面试一定会问。我整理了一个自检清单你可以对照检查数据结构与算法方向能否3分钟内bug-free写出反转链表能否解释KMP算法中next数组的含义并手算能否说出快排什么时候会退化到O(n²)能否推导Dijkstra算法的正确性能否用单调栈解决下一个更大元素问题机器学习方向能否推导线性回归的最小二乘解能否解释逻辑回归的损失函数为什么用交叉熵能否说明L1和L2正则化的区别能否画出决策树的构建流程能否解释GBDT和随机森林的区别业务与工程方向能否设计一个完整的推荐系统链路能否说明AB实验的流程与注意事项能否解释什么是冷启动问题能否说出特征工程常用的几个方向5.4 笔试失利后如何调整状态笔试没通过不代表你不适合这个岗位有时候只是准备方向有偏差。我自己也经历过笔试挂掉的情况复盘下来通常是两类原因一是时间分配不合理前面编程题卡太久后面的简答没时间写二是刷题偏科只刷了算法题机器学习基础没巩固。如果你笔试没过我的建议是先找到复盘的抓手记录自己每道题的答题时间和正确率看看到底是哪个模块拉跨。如果是编程题超时后面刷题就刻意练习限时完成如果是选择题概念不清就回炉看基础如果是简答题不会就需要多积累业务知识。实习笔试和秋招笔试的区别在于实习更看重潜力秋招更看重综合能力。一次笔试失败不要影响心态把错题整理好下一个机会很快会来。6. 写在最后的几点经验这篇复盘写到这里核心内容基本讲完了。回顾蘑菇街2019届实习生算法工程师的笔试我个人最大的体会是题目本身并不偏甚至可以说是“中规中矩的典型电商算法岗试题”但正是这种中规中矩考察的恰恰是你是否把基础打扎实了。如果你正在准备类似公司的算法实习笔试我给你三条实操层面的建议第一刷题不要只盯着LeetCode牛客网上的历年真题也很有价值因为很多互联网公司的笔试题目风格和LeetCode不太一样更偏工程场景和业务结合比如TopK问题、字符串匹配、概率统计题。第二对于机器学习部分不用追求“每个模型都会推导”但至少要保证逻辑回归、决策树、朴素贝叶斯、K-Means这些经典模型的原理、损失函数、优缺点能讲清楚。搜广推方向的实习岗尤其要重视CTR预估链路和特征工程。第三笔试是脑力活也是体力活提前睡好、准备好草稿纸、调试好编程环境这些细节看似不起眼但在紧张的考试状态下真的会影响你的表现。我见过有同学在笔试时因为IDE的缩进设置不对白白浪费了10分钟调试。最后分享一个小技巧笔试中如果遇到完全不会的编程题不要直接放弃写出暴力解法、提交一个部分正确的结果往往也能拿到一部分分数。有些笔试的评测用例是分档的暴力解法能跑过前面的小数据用例这比直接交白卷要好得多。希望这份复盘对你有帮助祝准备笔试的同学都能顺利过关。