美团2016研发工程师笔试题（三）复盘：算法与基础考点全解析

聊到美团2016研发工程师笔试题三很多准备校招的朋友都喜欢问第三套到底考什么、难度怎么样、有没有参考价值。说实话这套题离现在有些年头了完整原卷很难逐字还原但考点分布、题目难度、易错点设计我是记得比较清楚的。网上能找到的回忆版也比较零散这篇就按当年的题型结构做一次完整复盘用同考点、同难度的练习题带你过一遍。下面的示例题都是我按当年常见考点整理的同类题不是原卷一字不差的内容但题型和考察方式足够贴近。这套内容适合三类人看正在刷题备考的应届生想评估自己基础扎实程度的转行者以及准备出模拟题的技术面试官。先说结论美团笔试的风格和其他互联网大厂很像算法题是重头戏但计算机基础题的比例同样不低。“研发工程师笔试题三”与一、二套相比最大特点是基础题覆盖更细还夹杂着一两道“看起来简单、实则考边界条件”的题专门筛掉只会背模板、不会做复杂度分析的人。下面我从试卷布局、算法题、计算机基础、逻辑推理和复盘备考五个方向展开。1. 试卷整体布局可别小看这套题的价值1.1 题型结构与分值占比那几年的互联网校招笔试普遍分成两大块前面是客观选择题后面是编程题少数卷子会加填空题。美团2016研发工程师笔试题三的卷面结构按当年经验推断大概是单选/多选题约20到25题覆盖数据结构、操作系统、网络、数据库、编程语言基础、智力题整体分值占比约60%。这部分题量不小且基本没有送分题每个选项都可能埋坑。编程题约2到3题以在线评测系统限时提交要求在规定时间和内存内跑通分值占比约40%。编程题不会出特别偏门的数据结构重点在基础算法和边界处理。有人可能会问既然岗位是研发工程师为什么算法只占40%这其实是有意设计的筛选逻辑。选择题能快速过滤掉知识面窄的人编程题能过滤掉动手能力差的人两者结合既能筛掉“背了一堆理论但写不出代码”的也能筛掉“代码能力强但底层基础薄弱”的。很多同学只重刷题不重基础最后反而挂在选择题上这点需要特别留意。1.2 时间分配与答题顺序客观题题量大单题平均分配时间尽量不要超过90秒。我当时比较实用的策略是先做自己确定会的基础题拿不准的先用排除法缩小范围并标个记号最后留出至少30到40分钟给编程题。很多人容易在一道概率计算题上死磕结果编程题没时间写这是最亏的。笔试不是满分制分数线看的是整体排名能拿到的分都要拿到拿不到的果断跳过。我建议用“先易后难、先客观后主观”的顺序推进。编程题如果一时没有最优解先写一版暴力解保证正确再讲清楚优化方向。笔试环境里暴力解通常能过部分用例至少不会空题。有些同学习惯按题号顺序答题遇到难题不动摇其实不是好习惯。一道题卡五分钟等于后面三到四道简单题的时间被吃掉非常不划算。2. 算法与数据结构拉开分差的主战场2.1 高频必考数组、链表和字符串的“三板斧”先说数组。美团那年特别偏爱“局部有序”的题目典型代表是找峰值元素。题目会给一个数组相邻元素不相等让你返回任意一个峰值下标而且要求时间复杂度做到O(log n)。第一次见这道题很多人会想直接遍历但遍历是O(n)不满足要求。正确解法是二分比较nums[mid]和nums[mid1]如果mid的值更大说明峰值在左半边把右边界收到mid否则峰值在右半边把左边界收到mid1。def find_peak(nums): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] nums[mid 1]: right mid else: left mid 1 return left为什么这样一定收得到峰值因为数组两端默认是负无穷而循环里始终朝着“存在上升趋势”的方向收缩最后收缩到的点一定满足“左边下降、右边也下降”的峰值定义。这道题难的不在代码而在你能不能跳出“二分只能用在完全有序数组”的思维定式。链表题里出现频率最高的是环形链表与快慢指针。常见问法有两种判断链表有没有环以及有环的话找到入环点。第一问很简单慢指针每次走一步快指针每次走两步如果有环两个指针必然相遇。第二问要先记住操作第一次相遇后把快指针重置到链表头再让两个指针都改为每次走一步下一次相遇的位置就是入环点。为什么成立从数学上讲第一次相遇时慢指针走的距离等于环长整数倍因此重置快指针后快指针从头走到入环点的距离和慢指针从相遇点继续走到入环点的距离在环的意义下相等两个指针一定会同步到达入口。严谨推导可以画图验证笔试时把这个结论背下来直接用就行。字符串题最有代表性的是最长回文子串。暴力枚举所有子串再判断是否回文复杂度是O(n^3)稍微优化到O(n^2)笔试基本就能过。中心扩散是性价比最高的写法枚举每个回文中心和半径分别处理奇数长度和偶数长度。很多同学会漏掉偶数回文的起点小技巧是直接枚举两个中心一个中心是i本身另一个中心是i和i1之间。def longest_palindrome(s): n len(s) ans for i in range(n): # 奇数长度 l, r i, i while l 0 and r n and s[l] s[r]: if r - l 1 len(ans): ans s[l:r1] l - 1 r 1 # 偶数长度 l, r i, i 1 while l 0 and r n and s[l] s[r]: if r - l 1 len(ans): ans s[l:r1] l - 1 r 1 return ans如果追求极致性能可以用Manacher算法做到O(n)但笔试场景下不建议优先写因为边界条件多、费时间O(n^2)方案往往已经足够。2.2 动态规划与贪心容易看走眼的送分题美团笔试历来爱考动态规划2016年最常出现的类型是“最少步数”“最大收益”这类最优化问题。比如给定一支股票每天的价格数组只能买卖一次求最大利润。这题本身不难只要维护历史最低价每天计算当天卖出能赚多少然后更新最大收益O(n)就能完成。但很多人会条件反射式地去找全局最低点和最高点忽略了“最低点必须在最高点之前”这个约束反而写错。def max_profit(prices): min_price float(inf) max_profit 0 for price in prices: if price min_price: min_price price elif price - min_price max_profit: max_profit price - min_price return max_profit另一类常见题是快速幂。题目会给一个很大的指数例如计算a^b % mod其中b可能达到10^18循环相乘必超时。正确做法是把指数按二进制拆解每右移一位底数就做一次平方复杂度降到O(log b)。这个技巧看起来像数学题其实是位运算和分治思想的结合非常值得背下来。def fast_pow(a, b, mod): res 1 a % mod while b 0: if b 1: res res * a % mod a a * a % mod b 1 return res这道题还有一个变种求斐波那契数列第n项n是10^18用递推O(n)也会超时。解决办法是用矩阵快速幂把递推式转成矩阵乘法仍然是O(log n)。这类题考的是同一个核心能不能把指数级操作的规模压下来。2.3 边界条件与复杂度判题系统里隐藏的“扣分点”有些同写算法思路完全没问题但在线评测就是跑不过大多数败在边界条件上。比如没有考虑空数组或单元素数组递归层数过深导致栈溢出或者链表节点为空时直接去访问next。笔试判题不像本地IDE那么友好它会把极端数据一股脑塞给你写代码前最好先在草稿纸上列出边界情况再开始动手。关于复杂度我有个习惯动手前先注释声明“时间复杂度O(什么)、空间复杂度O(什么)”。如果题目说n最大10^6你的O(n^2)解法大概率超时如果题目要求额外空间O(1)你就不能新开一个和原数组等长的辅助数组。笔试看的不只是“跑通”还有思路是否在可控范围一个明显超内存的解法就算结果对了也可能被判不过。3. 计算机基础网络、操作系统、数据库的选择题陷阱3.1 计算机网络TCP状态与三次握手的几种考法网络题几乎是每套笔试的必考点。美团2016研发工程师笔试题三里最喜欢考的是TCP连接管理。选择题经常这么出TCP建立连接需要几次握手断开连接需要几次挥手TIME_WAIT状态出现在连接的哪一端这里最容易被坑的是把TIME_WAIT记成出现在被动关闭方。实际它只出现在“主动关闭方”作用是保证最后一次ACK能到达对端同时让旧连接中的报文段在网络中自然消失。还有一个理论问法为什么TCP建立连接是三次握手而不是两次答案不是为了多一次通信而是防止失效的连接请求突然到达服务器。假如客户端发了一个SYN因为网络拥塞卡了很久客户端超时重发后终于建立连接并关闭这时候旧SYN又到达服务器服务器会认为这是一个新连接请求并分配资源。如果只有两次握手服务器就会白白建立一条无效连接三次握手可以通过客户端的最后一次确认来规避这个问题。理解到这个层面比单纯背“三次”两个字有用得多。3.2 操作系统进程线程、死锁与虚拟内存操作系统题也稳定占一定比例。死锁几乎是必考四个必要条件要知道互斥条件、持有并等待条件、不可剥夺条件、循环等待条件。选择题会给几个场景问能否造成死锁判断时要看是否同时满足四个条件。只要破坏其中一个就能预防死锁。比如把“持有并等待”改成“一开始就申请全部资源”循环等待就被打破了。进程和线程的区别也是高频题选择题常见的错误表述是“一个进程里的所有线程共享相同的栈”。实际上同一进程内的线程共享堆、全局变量和文件描述符但每个线程都有自己的栈、寄存器上下文和程序计数器。“谁负责分配资源、谁负责占用CPU”要分清楚进程是资源分配的基本单位线程是CPU调度的基本单位。这两个定义拿不准很多派生题都会跟着错。虚拟内存部分常见考点是页面置换算法最常考的是LRU最近最久未使用。理解LRU最好的办法是想一个双向链表配合哈希表的组合每次访问页面时把节点移动到链表头部淘汰时直接删尾部节点这样查询和更新都是O(1)。选择题可能会给一个访问序列让你算缺页次数这题没有技巧老老实实画表格最容易拿分。3.3 数据库索引失效与事务隔离级别的易错点数据库题集中在索引和事务。选择题常见问法什么情况下建了索引也不会生效有几个典型场景对索引列使用函数或计算比如WHERE YEAR(create_time) 2024LIKE以通配符开头比如LIKE %abc隐式类型转换比如索引列是VARCHAR条件写成WHERE name 123联合索引没遵循最左前缀匹配。这个考点很实用就算笔试过了以后写业务SQL也用得上。事务隔离级别有四种读未提交、读已提交、可重复读、串行化。MySQL默认是可重复读这个细节也经常考。易错点在区分名词一个事务读到另一个事务未提交的数据叫脏读一个事务里两次相同查询得到不同结果叫不可重复读。理解了场景再记概念比死记定义牢固得多。笔试如果给出具体场景先把场景对应到名词再对应到隔离级别正确率会高很多。4. 数学与逻辑推理容易被拉分的“怪题”4.1 概率期望题看似复杂入手点其实固定逻辑题在整套卷子里占比不大却经常是区分高分段的关键。常见的一类是等概率随机数生成典型如给你一个能等概率生成1到5的随机函数rand5要求写出生成1到7等概率随机数的rand7。很多人会想到两个rand5相加再取模但这样做每个数字概率并不均匀。标准解法是拒绝采样先用两次rand5组合出1到25的均匀分布只取1到21的数字映射到1到721以上的结果丢弃重采样。def rand7(): while True: x (rand5() - 1) * 5 rand5() # 均匀生成1到25 if x 21: return (x - 1) % 7 1拒绝采样的效率可以算一下单次成功概率是21/25失败后重新采样期望调用次数约1.19次完全可接受。笔试里如果考到这类题核心不是写多优雅的代码而是让考官看到你理解“均匀分布”的含义以及如何处理拒绝。还有一个高频概率题一只硬币抛到正面才停止抛掷次数的期望是多少答案是2因为几何分布的期望是1/pp1/2。如果再进阶一点两个人轮流抛硬币先抛到正面的人获胜先手获胜概率是多少答案是2/3而不是1/2。推导方式很简单先手第一轮赢的概率是1/2先手输掉第一轮后出现第二轮的概率是1/4第二轮赢的概率是(1/4)*(1/2)以此类推等比数列求和等于2/3。这类题的共同点是只要能把一次试验拆成独立事件剩下的计算都不难。4.2 非标准逻辑题用极端情况试出规律有些题信息量很少但冷静下来就能找到思路。最经典的例子是100层楼两个一样的鸡蛋要求找出一扔就碎的最低楼层最少尝试多少次可以保证找到很多人第一反应是二分但两个鸡蛋不够用二分思路会在鸡蛋不够时崩溃。正确思路是“让最坏情况的测试次数尽量均衡”。假设最优方案最多试x次那么第一次在x层扔鸡蛋如果碎了剩下一个鸡蛋只能从1楼逐层试到x-1楼最多再试x-1次加上刚才那次正好x次如果没碎下一次往上推进x-1层因为后面的可用次数只剩x-1次。最终需要满足x(x-1)(x-2)...1≥100左边是x(x1)/2解得最小x14。所以答案是14次第14层、第27层、第39层这么往上跳。这道题难在把“固定次数预算”反过来用而不是直接去求临界楼层。如果鸡蛋从两个变成K个问题就会升级为动态规划。设dp[moves][k]表示用moves次尝试和k个鸡蛋最多能覆盖多少层楼状态转移是dp[moves][k]dp[moves-1][k-1]dp[moves-1][k]1含义是“当前楼层碎了用掉一个鸡蛋、没碎保留所有鸡蛋再加上当前这一层”。笔试遇到这类题时先不要急着写代码手推几个小规模结果状态转移很快就清楚了。5. 复盘与备考建议把“做过”真正变成“会做”5.1 刷完题先做分类而不是急着刷下一套刷完一套美团2016研发工程师笔试题三如果只是对一遍答案这套题基本等于白做。我建议从三个维度复盘考点、错误原因、标准解法。错误原因比考点更重要一道题知道自己错在哪比做对十道题都值钱。我自己的习惯是建一个表格列“题号、考点、错误原因、正确思路、复杂度、同类题链接”六列。错误原因可能是“没考虑数组越界”“状态转移推错”“TCP状态记混”每一类对应不同的改进动作。整理过几十道题后会发现自己的薄弱点其实高度集中在几个位置针对性地补比盲目刷题高效得多。5.2 选择题的快速排除与验算技巧选择题不一定都要完整求解。第一原则是排除法优先先看有没有明显违反基本原理的选项。比如问死锁条件选项里出现“多个进程必须同时运行”这类表述只要抓住死锁的本质是“互相等待对方释放资源”就能快速判断这选项不对。排除法在节省时间上的作用远远大于一开始就硬算。数字类题目算出结果后要养成反向验证的习惯。概率题算出来先手胜率是2/3可以用“先手概率后手概率1”检查鸡蛋掉落题算出14次可以手推前几步看看方案是否成立。这个步骤花费不到30秒但能拦截大量低级计算错误。选择题的选项也经常有干扰项比如答案是2/3选项里常放一个1/2如果你算出1/2就要停下想是不是漏了“第一轮如果后手赢局面翻转”的情况。5.3 临场发挥别让一题卡住整张卷子笔试和面试一样考的不只是技术还有情绪控制。做过这套题的不少同学都反馈心态一旦崩后面连简单的递归题都会写乱。我当时给自己定了一条规矩选择题一道题最多看三分钟编程题最多看十分钟超过时间还没思路就先用暴力思路保底。这样安排的结果是整张卷子没题空着编程题也总能拿部分分。编程题交卷前有一个非常实用的小习惯花10秒钟扮演“测试用例机器”用两个小例子手动跑一遍核心循环。比如数组题用[1,2,3,4,5]和[5,4,3,2,1]各跑一遍链表题画一个两个节点的环字符串题试试空串和单个字符。大多数低级错误像下标越界、循环条件漏了等号都是靠这个习惯救回来的。笔试环境没有断点调试这种人工模拟就是最好的排错方式。最后再分享一个小技巧所有编程题写完哪怕时间再紧也要在注释里写清楚时间复杂度和空间复杂度。这不会被判题系统读取但会逼你自己再想一遍算法是否合理。美团这类公司的笔试不会只看最终结果代码里暴露出的思维习惯才是真正拉开差距的东西。