准备秋招算法岗的同学大概率翻过美团2017年那套笔试真题。我印象很深的是当时拿到算法工程师B卷第一反应是题目不难真正动手才发现选择题里全是概念细节编程题又有不少边界坑。后来复盘时我意识到这套卷子的价值不在于题本身多难而在于它非常典型地反映了大厂算法笔试考察的底层逻辑基础要扎实、边界要敏感、实现要稳。这次整理不是单纯把题目答案贴出来而是把每道题背后的考察意图、容易踩的坑、以及我当时在考场上的思考过程都拆开讲清楚。无论你是正在准备校招还是想补算法基础这套题都值得花时间慢慢过一遍。1. 当年那套B卷的游戏规则先看清再动手1.1 B卷的题目构成与分值分布美团2017年秋招算法工程师笔试分AB卷B卷整体结构是20道选择题加3道编程题考试时间90分钟总分100分。选择题每题2分共40分覆盖数据结构、算法设计、机器学习基础三个方向编程题每题20分共60分三道题分别是字符串、贪心、动态规划。从分值占比就能看出来编程题才是重头戏选择题更像是用来卡基础概念的。A卷和B卷的差异在于A卷偏重算法理论推导B卷更贴近工程实现场景。比如B卷编程题里有一道商品名称纠错问题本质上是编辑距离但套了一个业务背景这在A卷里不常见。如果你同时看过两套题会明显感觉到B卷在考察“能不能把学过的算法用到实际问题上”而不只是“会不会默写代码”。1.2 我当时的答题顺序策略90分钟做23道题时间看起来够但实际很紧。我吃过亏的地方是选择题花太多时间推公式。当时有一道关于朴素贝叶斯后验概率的题我硬算了五分钟算完发现编程题时间被压缩了。后来复盘我给自己的建议是选择题控制在30分钟以内拿不准的先标记跳过编程题先花两分钟扫一遍题面判断难易程度从最有把握的开始写。编程题我建议先做贪心那道再做字符串最后啃动态规划。原因是动态规划题就算思路对边界条件也容易写错需要留出调试时间。而贪心题只要排序策略想明白代码量小不容易出大问题。这个顺序不一定适用于所有人但核心原则是先把能拿稳的分拿到手再去挑战不确定的题。提示拿到卷子先别急着做题用2分钟整体扫一遍题目。判断每道题的难度和数据范围这对后续时间分配非常关键。2. KMP next数组一道题看清字符串匹配的功底2.1 题目原文与next数组的定义陷阱这套B卷选择题里有一道字符串题要求针对模式串pabacaba写出next数组。题干给出了next[i]的定义但问题就出在这个定义上。KMP算法里的next数组在不同教材里有好几种定义方式最常用的两种定义一失配跳转用next[i]表示模式串前i个字符组成的子串中最长相等前后缀的长度且令next[0]-1。失配时j指针跳到next[j]。定义二最长前后缀长度next[i]表示模式串p[0]到p[i]这个子串的最长相等前后缀长度不含自身。这两种定义算出来的数组不一样。当年很多人直接背了某个版本的模板就上考场看到题目里给的next[i]定义和模板不一致当场就懵了。我当年还算幸运考试前专门研究过两种定义的差异在答题时先标明“我采用失配跳转定义”再从定义出发推导才没有踩坑。2.2 逐位手算abacaba的next数组我用失配跳转定义来逐位推导。模式串pabacaba长度为7所以next数组从next[0]到next[6]一共7个值。next[0]约定为-1表示第一个字符失配时模式串指针无法再回退需要移动文本串指针。next[1]看p[0]a单个字符没有真前后缀最长相等前后缀长度为0所以next[1]0。next[2]看p[0..1]ab前缀有a后缀有b不相等next[2]0。next[3]看p[0..2]aba前缀a、后缀a相等长度1前缀ab、后缀ba不相等所以最长相等前后缀长度是1next[3]1。next[4]看p[0..3]abac前缀a、后缀c不相等前缀ab、后缀ac不相等前缀aba、后缀bac不相等next[4]0。next[5]看p[0..4]abaca前缀a、后缀a相等长度1前缀ab、后缀ca不相等前缀aba、后缀aca不相等前缀abac、后缀baca不相等所以next[5]1。next[6]看p[0..5]abacab前缀ab、后缀ab相等长度2前缀a、后缀b不相等前缀aba、后缀cab不相等再长的前缀后缀也不匹配所以next[6]2。最终结果next [-1, 0, 0, 1, 0, 1, 2]。如果按照第二种定义把next[i]理解为p[0..i]的最长相等前后缀长度那结果就变成[0, 0, 1, 0, 1, 2, 3]。两个结果差了整整一位的错位关系只是定义变了输出完全不一样。所以做这道题第一件事永远是确认题目给的定义。2.3 next数组的计算代码与匹配流程next数组的递推代码非常简洁但理解起来需要一点时间vectorint buildNext(const string p) { int m p.size(); vectorint nxt(m); nxt[0] -1; int j 0, k -1; while (j m - 1) { if (k -1 || p[j] p[k]) { j; k; nxt[j] k; } else { k nxt[k]; } } return nxt; }代码里k表示当前匹配到的最长相等前后缀长度。当p[j] p[k]时说明前后缀可以继续扩展所以把k加1赋给nxt[j1]当不相等时k回退到nxt[k]这个回退过程和KMP匹配失配时的回退逻辑完全一致。我第一次学这段代码时也觉得很绕后来把递归回退过程手推了几遍才真正理解。匹配流程举个例子就更清楚了。模式串abacaba在文本串ababacaba中匹配前4个字符abab匹配成功第5位文本串是a模式串是c失配。此时j4查next[4]0模式串指针跳到p[0]即用a去和当前的文本串第5位a比较匹配成功。继续往后匹配最终在文本串第8位处找到完整匹配。整个过程跳过了大量重复比较这就是KMP比朴素匹配高效的原因。笔试如果考到KMP不太可能要求背代码但很可能会让你手算next数组或者在选择题里问某个失配场景下j该跳到第几位。这两种考法都需要你对next数组的定义和计算过程有清晰理解而不是模糊记得模板。2.4 考场上遇到定义分歧怎么处理这里说一个我后来才想明白的考场经验遇到next数组题目如果题干里给了定义就严格按定义计算如果题干没给定义优先按失配跳转的常见定义算同时可以在答题区写一句“按失配跳转定义计算”作为保险。如果你追求严谨在计算完成后可以做一个验证随便选一个位置比如next[6]2含义是p[0..5]abacab的最长相等前后缀长度为2即ab和ab。验证方法就是把这个子串的前2个字符和后2个字符都写出来对比是否相等。这个验证过程花不了20秒但能有效防止因定义理解偏差导致的整题失分。3. 区间调度问题贪心策略为什么要按结束时间排序3.1 题目背景与输入输出约定B卷第二道编程题是一道区间调度题。题目大概是给定n个时间区间每个区间表示一个商户的配送时段用[start, end]表示要求选出尽量多的区间使它们互不重叠输出最大数量。这个背景一看就是从美团外卖的配送场景抽象出来的很典型的业务驱动型考察。输入约定n不超过10万每个区间的start和end都是整数范围允许为负数。输出是最大的不重叠区间数量。数据范围n10^5这个信息很关键它直接暗示你应该往O(n log n)的算法方向想排序加一趟扫描而不是O(n^2)的动态规划。3.2 三种排序策略的对比与反例做区间调度直觉上可能想到按开始时间排序、按区间长度排序、按结束时间排序三种策略。这里直接给结论只有按结束时间升序排序然后用贪心法依次选择才能保证得到最优解。按开始时间排序为什么不对举一个反例区间集合为[1,6]、[2,4]、[5,7]。按开始时间排序会先选[1,6]但[1,6]同时覆盖了[2,4]和[5,7]最终只能选1个区间。而最优解是选[2,4]和[5,7]共2个区间。这个反例很直观地说明了问题开始早的区间不一定好它可能横跨多个小区间把后续选择全堵死。按区间长度排序同样是个常见的错误直觉。它的逻辑是“先选短的占用空间少就更容易塞下其他区间”听起来很合理但同样可以构造反例。反正记住一个事实区间调度的正确贪心策略只有按结束时间排序这一种其他排序方式都是错一半的直觉。3.3 完整解法与边界条件按结束时间排序的完整解法写法struct Interval { int start, end; }; int maxNonOverlapping(vectorInterval intervals) { if (intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; }); int count 0; int lastEnd INT_MIN; for (const auto iv : intervals) { if (iv.start lastEnd) { count; lastEnd iv.end; } } return count; }核心逻辑是每次选择当前结束时间最早的区间然后跳过所有与之重叠的区间再选择下一个结束时间最早的区间。这里有两个边界条件容易出错。第一个是重叠判定。题目如果规定两个区间端点相接不算重叠就用iv.start lastEnd表示可以同时选如果端点相接也算重叠就要改成iv.start lastEnd。这个细节直接关系代码里的比较符号写反了要么多选区间要么少选区间。我在考场上就因为这个纠结了一会儿浪费了两分钟。第二个是区间的起始值范围。因为允许负数所以lastEnd要初始化成INT_MIN而不能是0。不然第一个区间的start如果是负数会被判定为重叠而错误跳过。提示遇到区间类问题先确认题目对“重叠”的定义端点相接算不算重叠。这个坑在笔试和面试里都频繁出现不是小题大做是真能扣分。3.4 带权版本的扩展思路如果这道题再增加一个条件每个区间带一个权重要选出的区间总权重最大贪心就不成立了。带权重时必须用动态规划按结束时间排序后定义dp[i]表示前i个区间能获得的最大权重转移时要么不选第i个区间要么选第i个区间并加上前面最后一个与它不重叠的区间的dp值。查找那个不重叠区间可以用二分优化到O(n log n)。这个扩展版本当年没考但我在面试里被问过衍生问题。如果时间充裕建议把带权版本也练一遍。它能帮你理解贪心和动态规划各自适用的场景而不是机械地背题。4. 编辑距离动态规划状态设计的经典范式4.1 业务背景与题目描述B卷第三道编程题套了一个商品名称纠错场景商家后台导入商品时系统需要把两个商品名之间的编辑距离算出来距离越小说明越可能是同一款商品。输入两行字符串输出最小编辑操作次数允许的操作为插入一个字符、删除一个字符、替换一个字符。这个问题就是经典的编辑距离Levenshtein Distance。我当时看到题就意识到它考的不是能不能写出状态转移方程而是能不能把状态定义、初始化、边界条件一次性写对。很多同学对dp[i][j]表示什么其实没想透只是背模板一换场景就漏掉细节。4.2 dp数组状态定义与转移方程定义dp[i][j]表示字符串word1的前i个字符转换成word2的前j个字符需要的最少操作次数。这个定义里i和j都是从0开始计数的dp[0][j]表示从空串转换成word2的前j个字符只能通过插入操作代价为jdp[i][0]表示从word1的前i个字符转换成空串只能通过删除操作代价为i。转移方程分两种情况如果word1[i-1] word2[j-1]说明当前字符相同不需要额外操作dp[i][j] dp[i-1][j-1]。如果不相同取三种操作的最小值再加1dp[i-1][j] 1删除word1的第i个字符dp[i][j-1] 1在word1中插入一个字符使其等于word2的第j个字符dp[i-1][j-1] 1把word1的第i个字符替换成word2的第j个字符代码实现int minDistance(string word1, string word2) { int n word1.size(), m word2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 0; i n; i) dp[i][0] i; for (int j 0; j m; j) dp[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { if (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1; } } } return dp[n][m]; }这里有一个新手容易犯的错把字符比较写成word1[i] word2[j]。因为dp数组的下标从1开始表示“前i个字符”而字符串本身下标从0开始所以第i个字符应该用word1[i-1]访问。这个偏移量问题如果不仔细很容易在写代码和调试时来回折腾。4.3 手推一遍horse到ros的完整过程以word1horseword2ros为例手动推一遍二维dp表的过程。先初始化dp[0][0]0dp[1][0]1dp[2][0]2一直到dp[5][0]5dp[0][1]1dp[0][2]2dp[0][3]3。然后从i1, j1开始填表dp[1][1]word1[0]hword2[0]r不相等min(dp[0][1], dp[1][0], dp[0][0]) 1 min(1, 1, 0) 1 1。dp[1][2]h vs o不相等min(dp[0][2], dp[1][1], dp[0][1]) 1 min(2, 1, 1) 1 2。dp[1][3]h vs s不相等min(dp[0][3], dp[1][2], dp[0][2]) 1 min(3, 2, 2) 1 3。继续填到dp[5][3]最终得到3。转换路径是horse → rorseh替换为rrorse → rose删除第二个rrose → ros删除末尾e。手推一遍的价值在于你能直观看到dp表的每一格都承接了之前计算的子问题。很多人在推导时容易忘记“替换操作代价是1”在dp表里对应的是左上角即dp[i-1][j-1]而“删除”对应正上方“插入”对应正左方。把这三个方向记清楚坐标就不会写反。4.4 空间优化与笔试中的复杂度要求二维dp的空间复杂度是O(n*m)对于笔试来说通常够用。但如果n和m都到10^3二维数组需要10^6个int内存还能接受如果到10^4就需要考虑优化。观察转移方程可以发现dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]也就是上一行和当前行的信息。所以可以用一维数组滚动更新。关键是要在更新dp[j]之前保存dp[j]的旧值这个旧值就是dp[i-1][j-1]。int minDistance(string word1, string word2) { int n word1.size(), m word2.size(); vectorint dp(m 1); for (int j 0; j m; j) dp[j] j; for (int i 1; i n; i) { int prev dp[0]; dp[0] i; for (int j 1; j m; j) { int temp dp[j]; if (word1[i - 1] word2[j - 1]) { dp[j] prev; } else { dp[j] min({prev, dp[j], dp[j - 1]}) 1; } prev temp; } } return dp[m]; }笔试中如果题目只要求输出最小编辑次数一维优化完全够用如果要求输出具体编辑方案就必须保留完整二维表。我当时的做法是先写二维版本保证正确性如果时间充裕再改为滚动数组。在时间不够的情况下保证正确比追求空间更省心所以不要一上来就优化先把正确的解法写出来更重要。5. 选择题里容易被小看的机器学习考点5.1 朴素贝叶斯一道题把条件概率算明白B卷选择题里有一道让我印象深刻的概率题某事件A发生的先验概率P(A)0.01检测方法的灵敏度P(B|A)0.95误报率P(B|¬A)0.05。问检测结果为阳性时A真正发生的概率最接近多少。解法是套贝叶斯公式P(A|B) P(B|A) * P(A) / (P(B|A) * P(A) P(B|¬A) * P(¬A))代入数值P(A|B) 0.95 * 0.01 / (0.95 * 0.01 0.05 * 0.99) 0.0095 / (0.0095 0.0495) 0.0095 / 0.059≈ 0.161答案约为0.16而不是直觉上感觉的0.95。这个例子我到现在都记得因为它完美展示了一个反直觉的结论在先验概率极低的情况下即使检测灵敏度很高阳性结果对应的实际概率也可能很低。这个题的考察点在于你不仅需要记住贝叶斯公式还要理解“先验概率”在结果中发挥的重要作用。美团这种业务导向的公司特别爱考这类题因为电商、交易、风控场景里到处是“小概率事件高灵敏度检测”的情况懂贝叶斯思维的人写出来的策略才不会过于激进。5.2 熵与信息增益背后的直觉另一类常考选择题是信息熵的计算。比如给一个二分类数据集正样本5个负样本3个问数据集的熵是多少。熵的公式H(X) -Σ p(x) * log2(p(x))代入数值H -(5/8 * log2(5/8) 3/8 * log2(3/8))≈ -(0.625 * (-0.678) 0.375 * (-1.415))≈ 0.954如果正负样本各4个熵就是1这是纯度为最不均衡状态下的最大值。熵越大说明数据越混乱信息增益就是划分前后熵的差值决策树选特征时选择信息增益最大的特征本质上是在选“哪个特征能让数据从混乱变有序的幅度最大”。我当时复习时经常忽略这类计算题觉得太基础。但笔试里它会以一种很绕的方式出现比如把熵的计算和条件熵结合问某个特征划分后的信息增益是多少。碰到这种题沉下心一步步算公式本身不难难的是不要被选项里接近的数值迷惑。提示机器学习概念题里最常见的失分原因是“知道公式但不会快速代入数值”。考前建议至少手算10道熵、贝叶斯、期望相关的计算题不需要用计算器练到笔算不出错。5.3 特征选择三类方法与过拟合辨析还有一道选择题涉及特征选择选项里混了过滤式、包裹式、嵌入式三种方法。常见套路是给一个描述问属于哪一类。过滤式Filter不依赖后续模型先对特征做统计指标筛选比如方差选择、卡方检验、互信息。包裹式Wrapper把特征子集的选择交给模型评估比如递归特征消除RFE。嵌入式Embedded在模型训练过程中自动完成特征选择典型代表是带L1正则化的线性模型稀疏解天然起到了特征选择的效果。L1正则为什么能产生稀疏解原因是L1范数在零点不可导优化过程中最优解更容易落在坐标轴上对应有些特征的权重被压缩到0。这个点经常考而且容易和L2正则混淆。L2正则不会让权重精确为0只会让权重整体变小所以它用于防止过拟合而不是做特征选择。过拟合的解决方案也是选择题重灾区。有效手段包括增加训练数据量、降低模型复杂度、加入正则化项、做交叉验证、进行特征选择。干扰项通常是“增加模型复杂度”和“减少训练数据”这两项看起来和过拟合沾边实际是反向操作。做题时看到这类选项要立刻识别出来它们是送分题的干扰项也是拉分题的关键。6. 复盘总结笔试后我才真正想明白的几件事6.1 数据范围是出题人给你的提示现在回头看这套B卷我觉得最有用的一个习惯就是从数据范围反推算法。n10^5基本排除O(n^2)暴力n1000可以考虑O(n^2)动态规划n20八成是状态压缩m和n乘积在10^6量级时二维dp安全超过10^7就得换思路。这个习惯不是天生的是刷题刷出来的。我准备笔试的时候每道题在动手前先看数据范围在草稿纸上写下“本题允许的复杂度上界”然后才想算法。这个习惯帮我避免了很多“想不出log算法就硬写暴力”的情况。针对美团这套题区间调度那道n10^5直接指向排序加贪心编辑距离那道如果n和m都给到1000二维dp正合适这些都和数据范围对得上。6.2 边界条件不是细节而是得分点这套卷子里的边界坑特别多next数组的定义、区间端点相接算不算重叠、编辑距离字符串下标偏移、概率题里的误报和漏报。任何一个处理错轻则答案偏差重则整道题崩溃。我见过太多人笔试成绩不理想不是不会做而是“会做但没做对”根源基本都在边界条件上。建议平时练题时养成一个习惯每写完一段核心逻辑主动问自己三个问题。第一个问题是数组下标有没有偏移第二个问题是最小值或最大值初始化对不对第三个问题是比较符号方向有没有可能写反这三个问题检查完代码基本就稳了。考场上没有时间让你大量测试主动在写代码时避免边界错误才是正道。6.3 笔试和面试考察的是同一种思维习惯笔试结束之后我又经历了几轮面试回头发现这套笔试题里的很多思维方式和面试官问的问题是一脉相承的。比如KMP的next数组面试时可能会换个形式问你“如何在一个长文本里高效查找多个短字符串”本质还是字符串匹配和状态转移区间调度会变成“如何给外卖骑手分配订单时段”编辑距离会变成“如何判断两个商户名是否相似”。算法知识点没变变的是场景包装。所以我后来给准备校招的朋友的建议是不要把笔试真题当作短期冲刺工具而是把它当成一次很好的算法思维体检。做对了说明对应的知识模块过关做错了不要只改个答案要顺着错误往下想一层找出到底是概念模糊、代码实现不熟、还是边界考虑不周。这套美团B卷覆盖的知识点不算偏基本都是高频基础考点把每道题背后的原理吃透比多刷十套新题更有价值。