2016年美团研发工程师的系列笔试题里第三套题我一直印象挺深很多候选人考完反馈是“看着不难拿分不易”。那会儿外卖大战正打得火热美团的技术团队扩张很快笔试题风格也跟业务贴得很近不玩偏题怪题但每道题都藏着小门槛。我后来跟朋友复盘这套题时发现它考察的东西其实很集中基础数据结构掌握得扎不扎实、边界条件想得全不全、能不能把业务场景抽象成代码逻辑。这些东西放到今天看依然是研发岗笔试的核心。这篇文章就把这套题里最有代表性的几类编程题拆开揉碎讲一遍包括每道题的考查意图、完整的解题思路和可运行的代码再补上一些我在实际工作中回头看才理解的工程化延伸。准备投互联网公司研发岗的同学或者想检验一下自己算法功底的开发者都可以拿这套题当试金石。1. 从这套题看2016年美团想要什么样的研发那几年美团的技术面试有一个很明显的倾向不看你背了多少八股文而是看你拿到一个具体问题时的处理方式。这套笔试题三的编程题部分整体难度在当时的校招题库里属于中等偏上但它有几个特点值得拎出来说。第一题目边界给得很清楚。每道编程题都会明确输入范围和时间限制但不会告诉你用哪种算法。比如配送路径相关的题点数量限制在16以内明摆着是让你在状态压缩动规和暴力的全排列之间做选择。你要是看不出这个数据范围的含义一上来就写个贪心或者压根没考虑复杂度基本就拿不到分。第二场景化包装比较多。题目很少直接说“求最短哈密顿回路”而是会包装成骑手送餐、仓库配货、多个取送点之间的路线规划。这其实是好事说明题目有真实业务背景不是纯粹为难人。但很多考生容易蒙觉得业务描述长读题就花掉好几分钟。实际上把业务外壳剥掉内核就是一道经典算法题。第三基础数据结构题占了很大比重。栈、队列、哈希表、链表、字符串处理这些是研发岗躲不开的基本功。第三套题里有个很有意思的现象越是看起来简单的题越能拉开分差。比如两个栈实现队列很多人在纸上画得明白一写代码就漏边界条件。这类题不存在“不会做”只存在“做得对不对、稳不稳”所以特别适合用来筛选代码习惯好的人。那会儿美团的业务正在高速扩张外卖、到店、酒旅多条线同时发力后端服务的并发量和业务复杂度都在涨。笔试筛选的目标很明确第一算法基础得够用不能连排序、二分、栈队列这些基本工具都拿不稳第二能把模糊的业务需求翻译成清晰的技术方案第三代码得干净最好是有工程习惯的人。这套题三基本就是冲着这三点设计的。放到现在的视角回头看这套题的价值依然在。虽然现在面试更强调项目和系统设计但笔试环节考察算法和编码底子的逻辑没有变而且题目里那些和业务场景结合的思路放到今天的面试里依然是加分项。2. 配送路径规划状态压缩DP的实际场景先说整套题里最像“压轴题”的一道。题目大致是这样外卖骑手从商家出发需要依次给N个用户送餐N不超过16。给定任意两个地点之间的距离矩阵骑手送完所有餐之后不需要返回商家求最短的配送路径长度。这道题有很强的时间限制暴力全排列只能过部分数据。这道题本质上是旅行商问题TSP的变体只是把“回到起点”去掉了。N的范围给到16是一个很明确的信号可以用状态压缩动态规划来做。你不需要真正走到每一个排列组合里去枚举而是可以把“已经送过哪些用户”压缩成一个整数的二进制位用 DP 数组记录当前状态下停留在某个用户位置时的最短路径长度。举个具体的例子。假设只有4个用户编号1到4加上起点0一共5个点。一个状态可以用一个5位的二进制数表示比如二进制10011表示已经访问过0号、1号、4号三个点当前停在4号点上。DP的推导逻辑就是从一个状态向下一个未访问的点转移新的距离等于当前距离加上两点之间的边长。核心代码大概长这样我用C写的语言不限但思路一致#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 16; const int INF 0x3f3f3f3f; int n; int dist[MAXN][MAXN]; int dp[1 MAXN][MAXN]; int solve() { memset(dp, INF, sizeof(dp)); // 初始状态只访问了起点0当前在0 dp[1][0] 0; for (int mask 1; mask (1 n); mask) { for (int i 0; i n; i) { if (!(mask (1 i))) continue; if (dp[mask][i] INF) continue; for (int j 0; j n; j) { if (mask (1 j)) continue; int nextMask mask | (1 j); dp[nextMask][j] min(dp[nextMask][j], dp[mask][i] dist[i][j]); } } } int ans INF; for (int i 1; i n; i) { ans min(ans, dp[(1 n) - 1][i]); } return ans; }这里有个容易搞错的点有些题目要求回到起点有些要求不回来。第三套题的表述是“不需要返回商家”那么最终答案就是所有送完所有用户、停在任意一个用户位置的状态里的最小值。如果题目改成“需要返回商家”最后还要加上dp[全访问状态][i] dist[i][0]别漏。状态压缩DP的复杂度是 O(2^N * N^2)N16时大约一千多万次运算在笔试限时下完全跑得动。相比之下全排列是 O(N!)N16时完全不可行。所以这道题的区分度就体现在这里你能不能从数据范围判断出该用哪种算法。我还想多说一句关于这道题的实际意义。TSP本身是一个NP难问题真实业务里骑手配送比这个复杂得多订单会实时进来、路况会变、用户不在家要打电话不可能真的用状态压缩DP去跑全量计算。但笔试考它不是指望你去解决真实调度问题而是考察你面对组合优化问题时的建模能力和复杂度意识。你在答卷里如果能先分析数据范围再给出DP状态定义和转移方程最后再说一句“数据量更大时需要换用启发式算法”这个回答就比纯贴代码高一档。3. 栈与队列的变体题答出亮点才有区分度第三套题的选择题和编程题里栈和队列出现了好几次其中“用两个栈实现一个队列”是当年笔试中出现频率非常高的一道。不少同学觉得这题简单但真正做到满分其实不容易。我先说这道题的标准解法再讲它的变形和易错点。栈是后进先出队列是先进先出。要用两个栈模拟队列核心思路是一个栈负责入队一个栈负责出队。入队时只往入栈压出队时如果出栈为空就把入栈里所有元素依次弹出并压进出栈这样元素的顺序就反过来了再从出栈弹出就是队头元素。class MyQueue { private: stackint inStack; stackint outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); } int pop() { transfer(); int top outStack.top(); outStack.pop(); return top; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这道题有三个常见的扣分点。第一个transfer函数只在outStack为空时才执行如果outStack还有元素却仍然从inStack里倒数据队列顺序就乱了。第二个pop之前必须检查队列是否为空否则调用outStack.top()会未定义行为有些笔试题会专门卡这个点。第三个不要在主函数里反复创建对象或者输出多余调试信息这会影响在线判题的结果。这道题在整套试卷里的位置往往靠前属于“热身题”但它后面经常跟着一道变形题“实现一个支持push、pop、top和getMin的栈要求getMin的时间复杂度为O(1)”。最小栈的解法是维护一个辅助栈每次push时把当前元素和辅助栈顶的较小值压入辅助栈。这样辅助栈栈顶始终是当前栈内最小值。class MinStack { private: stackint dataStack; stackint minStack; public: void push(int val) { dataStack.push(val); if (minStack.empty() || val minStack.top()) { minStack.push(val); } } void pop() { if (dataStack.top() minStack.top()) { minStack.pop(); } dataStack.pop(); } int top() { return dataStack.top(); } int getMin() { return minStack.top(); } };注意上面代码里的条件是val minStack.top()用的是小于等于而不是小于。如果改成小于当两个相同的最小值连续入栈其中一个被pop掉之后辅助栈里就找不到那个最小值了getMin就会出错。这个细节我在不少面试题解里都看到有人踩坑。从工程角度看栈和队列的变体题看着基础但它们在真实系统里的投影无处不在。调用栈、函数递归、浏览器页面的前进后退、消息队列、任务调度底层都能看到这两种数据结构的影子。美团这类O2O业务里订单推送的顺序控制、促销状态的流转都会用到队列。笔试考这些东西本质上是在考你有没有真正理解数据结构的语义而不是死记硬背API。4. LRU缓存模拟笔试里的高频考点第三套题里有一道让不少人纠结的题模拟LRULeast Recently Used缓存淘汰策略。题目要求实现一个固定容量的缓存支持get和put两种操作当容量满时淘汰最久未被访问的键值对。这道题考的是你对哈希表和链表的综合运用能力。有一种简单的思路是用数组加时间戳每次访问或插入时记录时间缓存满时扫描一遍找时间戳最旧的删掉。这个思路能过部分测试点但get和put的时间复杂度都退化成了O(n)在数据量大时没法看。标准解法是哈希表加双向链表。哈希表负责O(1)地找到某个key对应的链表节点双向链表维护访问顺序链表头部是最近访问的链表尾部是最久未访问的。每次get把命中的节点移到头部每次put如果key已存在就更新值并移到头部如果不存在且缓存已满就删除尾部节点再把新节点插到头部。用C标准库实现会简洁很多因为list本身是双向链表unordered_map存迭代器即可class LRUCache { private: int cap; listpairint, int cacheList; unordered_mapint, listpairint, int::iterator mp; public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { auto it mp.find(key); if (it mp.end()) return -1; cacheList.splice(cacheList.begin(), cacheList, it-second); return it-second-second; } void put(int key, int value) { auto it mp.find(key); if (it ! mp.end()) { it-second-second value; cacheList.splice(cacheList.begin(), cacheList, it-second); return; } if (cacheList.size() cap) { auto last cacheList.back(); mp.erase(last.first); cacheList.pop_back(); } cacheList.emplace_front(key, value); mp[key] cacheList.begin(); } };splice操作是O(1)的它能把链表节点直接从原位置移动到头部不需要拷贝。如果你自己手写双向链表同样能达到O(1)的get和put。很多候选人这里会写错常见的问题是更新已存在节点时忘记调整节点在链表中的位置删除尾部节点时忘记同步删除哈希表里的映射容量为0时没有做特殊处理。LRU这道题考得这么高频因为它背后是真实的系统设计问题。美团这种体量的平台用户请求的餐厅列表、骑手位置、商家菜单都是热点数据不可能每次都查数据库必须做多级缓存。而缓存一定会满淘汰策略就非常重要。LRU本身是一个经典的策略但真实场景里单一LRU是不够的。比如外卖App首页的餐厅列表如果按LRU淘汰一个用户偶然访问的冷门餐厅可能会把热门餐厅挤出缓存。所以工程上会有LRU的变体比如LRU-K访问K次才算热点、2Q、Arc等算法也会配合过期时间、主动淘汰、分片缓存来设计。笔试的时候如果你能在代码之外用注释或者答题区里补上一句“真实系统中还需要考虑并发控制和过期时间”这会让阅卷人对你的工程素养有印象。但注意不要在主代码里写一堆与判题无关的注释或者试图自己搞个线程安全的加锁版那是画蛇添足。还有一点想提醒这道题有时候会换一层皮出现比如“LFU缓存”“根据访问频率淘汰”或者“设计一个支持过期时间的缓存”。如果你把LRU吃透了迁移到LFU并不是难事。LFU需要维护每个key的访问频次通常用两个哈希表加最小堆或者用多重链表。笔试遇到变形题不用慌核心都是“如何用合适的数据结构让每种操作维持较低复杂度”。5. 满减券选择与业务模拟题考察对约束条件的敏感度第三套题里还有一类题很容易被低估就是带业务规则的模拟题。最有代表性的一道是满减优惠券的最优选择问题。题目大概是用户下单金额为M元平台发放了N张满减券第i张券的使用门槛是threshold[i]订单金额满threshold[i]元才可用可抵扣金额是discount[i]每一单只能使用一张券请问用户应该选择哪张券可以获得最大优惠。这道题很多考生一上来就想复杂了有人直接写了个背包有人甚至去写DFS枚举所有券的组合。但仔细读题“每一单只能使用一张券”这个约束才是关键。既然只能用一张那解法其实就是一个O(n)的遍历遍历所有券找出所有threshold[i] M的券里面discount[i]最大的那张。#include cstdio #include algorithm using namespace std; const int MAXN 100005; int n, M; int threshold[MAXN]; int discount[MAXN]; int main() { scanf(%d%d, n, M); for (int i 0; i n; i) { scanf(%d%d, threshold[i], discount[i]); } int ans 0; for (int i 0; i n; i) { if (M threshold[i]) { ans max(ans, discount[i]); } } printf(%d\n, ans); return 0; }如果题目改成“可以叠加使用多张券但券之间可能有互斥关系”那确实就变成一个NP难问题需要用搜索或者动态规划来求解但笔试里一般不会考到那么深考得深也基本是在问思路而不是要求完整实现。这道题真正的考点在于你能不能识别出业务规则背后的限制条件然后用最简单的算法解决。我在实际面试中见过很多候选人花了大量时间写了一个复杂的叠加优惠计算方案结果连“只能用一张”这个条件都没注意最后不仅超时还得不了分。审题尤其是业务模拟题的审题真的比写代码更重要。类似的题目还有比如“根据关键词匹配商家标签”“模拟购物车结算顺序”这类。它们的特点是一样的描述了一大段业务场景但核心逻辑并不复杂。做这类题的策略我总结成一句话先找约束条件再找数据范围最后才动手写代码。约束条件决定了模型复杂度数据范围决定了算法选择这两个信息都清楚了代码往往水到渠成。这类题在工程上也有直接的对应。优惠券、满减、红包这些营销玩法在美团 App 里都是非常核心的业务模块。真实系统里一张订单可能涉及多个优惠活动的叠加规则、互斥规则、优先级顺序这些规则不是靠一个数组循环就能算完的性能要求高的时候会用规则引擎配合缓存和降级方案。笔试里让你做的虽然是一个简化版本但培养的思维模式是一致的在复杂的业务规则里找到关键约束把它转化为可计算的模型。6. 阅卷人视角这些错我批了太多份最后这部分想聊点备考时不容易看到的内容。我不止一次跟同事聊起笔试阅卷的体验第三套题的答题情况其实很有代表性。很多同学不是不会做而是“会做但没拿满分”甚至拿不到一半分数原因集中在下面几类。第一类读题不完整。题目明明写了“输入数据保证至少存在一张可用券”还有人写代码时做一堆无意义的空值判断把简单题写复杂。反过来题目如果没写“保证数据合法”有些人就默认一定合法不做任何边界处理导致数组越界或者容器访问空元素。正确做法是读题时把题目中每一个约束条件圈出来明确哪些数据是保证的哪些数据可能非法。第二类代码没有自测意识。笔试环境不是写个函数就完事了很多题目要求处理多组输入或者有特殊边界值。我见过太多代码主函数里只处理了一组数据或者循环读取输入时没有正确处理结束标志。提交之前花十几秒构造一个最小用例和最大用例跑一遍是成本最低的涨分手段。第三类时间分配失衡。编程题往往不止一道有些同学在一道题上死磕哪怕已经卡了四十分钟还不放手导致后面的题完全没时间做。以第三套题举例前面的栈队列题和优惠券题属于“拿分题”后面的路径规划题属于“拉分题”。合理策略是先把所有拿分题干净利落做掉再回头啃拉分题。哪怕拉分题只写一个暴力解法也能拿到部分测试点的分数比空白交卷强太多。第四类变量命名和代码风格过于随意。笔试的代码虽然不直接跑在线上但阅卷人是有权给“代码印象分”的。int a[N]、int x、int y满天飞和threshold[]、discount[]、dp[mask][last]这种有语义的命名给阅卷人的感受完全不同。我建议平时刷题时就养成用有意义的变量名、写简短注释的习惯这不是浪费时间是提前为面试和代码评审做练习。第五类不会分析复杂度。很多同学写完代码就算完成任务从来不评估自己算法的运行时间。笔试的判题系统是有时间限制的一个O(n^2)的算法处理n10^5的数据基本必挂。答题时写代码前先算一下最坏情况下的操作次数超过10^8就要换思路这是一个非常实用的衡量标准。说回备考这件事。现在市场上刷题平台很多题目数量也远超2016年但核心考点变化不大。我个人建议如果目标是互联网公司的研发岗重点刷这几类题数组和字符串处理、链表操作、栈和队列变体题、二叉树遍历与递归、基础动态规划、排序和二分、哈希表应用。这些是笔试出现频率最高的方向。刷题的时候不要只追求AC每次提交后复盘一下自己的代码哪里可以优化有没有更简洁的数据结构可以用慢慢积累的才是真正的算法思维。最后分享一个我处理这类历史笔试题的体会。2016年的题放到今天部分考点已经被新的面试形式覆盖掉了比如现在更看重分布式和微服务背景但算法题考察的底层能力——建模、边界思考、复杂度权衡——始终没有变。你把这套题吃透了收获的不仅是几道题的解法更是一种面对任何技术问题时都适用的拆解路径先把问题读明白再找数据范围再设计解法最后落地成干净的代码。