2016年美团研发工程师的笔试题放到今天来看依然很有嚼头。那几年正好是移动互联网业务爆发、O2O大战打得最凶的阶段美团的笔试题目既保留了传统互联网公司对数据结构与算法的硬核考察又加入了大量贴近工程实践的思维题。我自己当年刷过这套题后来也帮学弟学妹们做过好几次复盘最大的感受是这套题表面考的是知识点实际考的是你在时间压力下拆解问题、快速建模、写出可运行代码的综合能力。这篇文章我会把“美团2016研发工程师笔试题(一)”里的核心考点、解题思路、现场策略和容易踩的坑整体过一遍。适合准备校招和社招笔试的同学参考也适合想检验自己基础功底的工程师拿来练手。我会尽量把出题人想考什么讲清楚而不是单纯给答案。1. 这套题到底在考什么先说清楚出题人的逻辑1.1 2016年前后的美团笔试画风2016年是美团业务快速扩张的时期研发岗位的需求量很大但笔试筛选一直很严格。这套笔试题的总体结构基本是选择题涵盖数据结构、操作系统、网络、数据库 编程题1到2道纯手写代码部分场次还有简答题。选择题的覆盖面很广但都不算偏门属于“你看过书就应该会但你没理解透就肯定选错”的级别。编程题则非常务实不会出那种需要冷门算法才能解的题而是把经典问题稍微包装一下考察你对基础数据结构的掌握和边界条件处理的熟练度。这和当年很多公司“炫技式”的出题风格不同。美团这套题更在意你是否具备“能干活”的工程基础而不是你是否记得某个冷门算法的模板。所以你会发现题目的文字描述往往带有一点业务场景的影子比如订单、配送、商家、用户之类的背景但剥掉外壳后内核还是那些经典的算法模型。1.2 笔试考察的能力模型算法思维、工程基础、临场判断我把这套题实际考察的能力拆成三个维度方便你对照自查。第一是算法思维。不是让你背算法而是看你在有限时间内能否把一个问题抽象成数据结构模型。比如看到“求最大区间和”能立刻想到动态规划或前缀和看到“判断链表是否有环”能立刻想到快慢指针。这种敏感度只能靠平时积累。第二是工程基础。操作系统、网络、数据库这些科目考的是你大学四年有没有认真听课。第三是临场判断。笔试时间通常很紧编程题往往只有三四十分钟。你能不能快速评估一道题的难度决定先写暴力解保底还是直接冲最优解这本身就是一种工程决策能力。有意思的是很多人在第三点上栽了跟头。明明会做的题因为死磕最优解导致最后没时间提交或者提交了但没跑通反而丢了分。这个后面我会专门讲。1.3 审题时最容易忽略的三件事复盘这套题的时候我发现有几个“审题陷阱”反复出现。第一个陷阱是题目给的输入范围。比如有的题告诉你数组长度最多是10^5那你就要意识到O(n^2)的暴力解大概率会超时必须往O(n log n)甚至O(n)的方向想。第二个陷阱是输出格式。有些题要求“输出最小下标”、“按字典序排序”之类的额外条件很多人写对了核心逻辑却在输出上栽了。第三个陷阱是边界情况。输入为空、只有一个元素、元素全部相同、目标值不存在……这些情况如果你在编码前没有在脑子里过一遍写出来的代码很容易在测试用例上挂掉。我后来给新人做笔试辅导时总是强调一句话审题花5分钟编码省20分钟。很多人觉得审题浪费时间上来就写代码结果写到一半发现理解错了推倒重来反而更慢。2. 算法与数据结构笔试的绝对主战场2.1 栈和队列最不值得丢分的送分题栈和队列是这套笔试题里最基础的考点但也是很多人丢分的地方。丢分不是因为不会而是因为不够细心。常见的考法是给你一个入栈序列和一个出栈序列判断这个出栈序列是否合法。比如入栈顺序是1、2、3、4、5出栈顺序是3、2、1、5、4这是合法的如果出栈顺序是4、3、5、1、2这就是非法的因为1在2之前入栈却在2之后出栈违反栈的LIFO原则。这类题的选择题版本很好做但编程题版本就有讲究了。核心是用一个辅助栈模拟入栈出栈过程依次将入栈序列的元素压入辅助栈每次压入后检查辅助栈栈顶是否等于出栈序列的当前指针如果相等就弹出直到不相等为止。最后如果辅助栈为空说明出栈序列合法。def is_valid_pop(push_seq, pop_seq): stack [] j 0 for x in push_seq: stack.append(x) while stack and stack[-1] pop_seq[j]: stack.pop() j 1 return len(stack) 0这段代码看起来简单但有个细节值得注意while循环里必须判断stack不为空否则当栈空时访问stack[-1]会抛异常。这种边界处理能力恰恰是笔试要考察的。我见过很多人在IDE里能跑通一到笔试环境尤其是白板写代码就忽略这种细节。2.2 字符串处理边界条件比思路更重要字符串相关题目在这套题里几乎必考因为字符串处理最能暴露一个人写代码的细心程度。常见的有反转字符串、判断回文、字符串匹配、最长公共前缀等。这里我挑一个很有代表性的题讲反转字符串中的单词顺序。比如输入“I am a coder”输出“coder a am I”。这个题的思路不难先整体反转再逐个单词反转。但很多人会在细节上翻车。def reverse_words(s): s list(s.strip()) # 先整体反转 s.reverse() start 0 n len(s) for i in range(n): # 遇到空格或末尾反转单词 if s[i] or i n - 1: end i - 1 if s[i] else i while start end: s[start], s[end] s[end], s[start] start 1 end - 1 start i 1 return .join(s)你仔细看这个实现麻烦不在于反转逻辑本身而在于处理单词边界最后一个单词后面没有空格所以循环里必须加i n - 1这个判断。另外多个连续空格怎么处理开头和结尾有空格怎么处理也是考察点。如果题目没有明确说明最好在代码里做容错或者至少在注释里说明你的假设。这类题给我的经验是字符串题永远不要只按“标准输入”写代码一定要考虑各种奇怪的边界情况。笔试的时候可以快速在草稿纸上列几个极端的测试用例比如空串、全空格、只有一个单词、单词之间有多个空格、标点符号等。2.3 链表与双指针一个套路吃遍天这套题里的链表题也比较多主要是链表反转、合并两个有序链表、找中间节点、判断是否有环等。链表题的核心技巧就是双指针和虚拟头节点。以“找到链表倒数第K个节点”为例。一种直接的做法是先遍历一遍得到链表长度再从头走N-K步。但更优雅的做法是用双指针让第一个指针先走K步然后两个指针同时前进当第一个指针到达末尾时第二个指针正好在倒数第K个位置。def find_kth_from_end(head, k): if not head or k 0: return None fast head slow head for _ in range(k): if not fast: return None # k超过链表长度 fast fast.next while fast: slow slow.next fast fast.next return slow注意我加了两个防御性判断k 0和fast中途变为None说明K超过链表长度。这些在笔试中都是加分项。很多候选人代码写得很漂亮但这些边界条件一个没处理面试官一眼就能看出工程经验不足。双指针还有一个非常经典的应用判断链表是否有环。快指针每次走两步慢指针每次走一步如果两者相遇则说明有环。这个方案空间复杂度是O(1)比用哈希表记录访问过的节点高效得多。如果题目进一步问“找到环的入口节点”就需要在快慢指针相遇后把其中一个指针移回链表头然后两个指针各走一步再次相遇的位置就是环入口。这个推导过程建议你自己推一遍理解了就不怕题目变形。2.4 动态规划入门题如何一眼识别状态转移动态规划在这套笔试题里属于压轴级别。2016年的题目里已经出现了一些经典的DP模型比如最长递增子序列、编辑距离、背包问题的变种。我拿“最长递增子序列”举例。这道题有两种典型做法O(n^2)的DP以及O(n log n)的贪心二分。笔试时如果你能写出O(n^2)的DP且正确处理边界已经能拿大部分分数如果你能进一步写出O(n log n)的版本那就是亮点。O(n^2)的DP思路dp[i]表示以nums[i]结尾的最长递增子序列长度。状态转移方程为dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。初始化时每个dp[i]至少为1因为单个元素本身就是一个递增子序列。def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)很多人在做DP题时最大的困惑是“怎么想到用DP的”。我的经验是看到题目要求最优解、最大/最小值、方案数等且输入规模在10^3到10^5之间大概率是DP或贪心。然后你去想“如果我知道前一个状态的最优解能不能推出当前状态”能推出来就是DP。笔试现场不需要你马上给出最优解你可以先写递归暴力再改成记忆化搜索最后改成递推DP。这个递进过程本身就是很好的解题思路展示阅卷时即使代码有瑕疵思路清晰也会给分。3. 操作系统、网络与数据库基础理论题的得分技巧3.1 操作系统进程调度、死锁、内存管理必考这套笔试题里的操作系统部分主要集中在三个方向进程与线程、进程调度算法、死锁的产生条件与处理策略。进程和线程的区别是高频题。选择题经常考“以下哪项不是线程独有的资源”答案是栈和寄存器。这背后的逻辑是线程共享进程的地址空间、文件描述符、全局变量等资源但每个线程必须有自己独立的栈用于函数调用和寄存器上下文用于保存执行状态。理解了这个无论题目怎么变都能答出来。死锁这块经典的四个必要条件互斥、持有并等待、不可剥夺、循环等待一定要背熟但更要理解为什么必须四个条件同时满足。比如“互斥”条件不是说资源只能一个进程用而是说资源不能同时分配给多个进程这是死锁的前提。笔试选择题很喜欢考“破坏哪个条件可以预防死锁”比如“资源一次性分配”破坏的是“持有并等待”“资源可剥夺”破坏的是“不可剥夺”。这些一一对应关系要清楚。内存管理方面页式存储是最常考的。有一个几乎必考的点逻辑地址到物理地址的转换。给你页表、页大小和逻辑地址让你算物理地址。计算步骤其实很机械先算出页号和页内偏移量再从页表中查出对应的物理页框号最后物理地址等于页框号乘以页大小加上偏移量。这个计算细则是页内偏移量的位数等于log2(页大小)逻辑地址的高位部分就是页号。很多人在进制转换上出错建议考试时多检查一遍计算过程。3.2 计算机网络三次握手、TCP与UDP、HTTP网络部分的考察重点我总结为“一条主线、三个协议”一条主线是TCP的连接管理三个协议是TCP、UDP、HTTP。TCP三次握手几乎是必考题但很多人的理解停留在“客户端发SYN、服务端回SYNACK、客户端回ACK”这个层面。笔试题目如果稍微深入一点问你“第二次握手的SYN和ACK分别代表什么”就有人答不上来了。第二次握手中的SYN是服务端向客户端确认“我收到了你的连接请求”同时SYN还表示服务端也希望与客户端建立连接ACK则表示对客户端SYN的确认。这两个标志位在同一报文里是为了减少通信次数。理解了语义你才能解释清楚为什么不是两次握手也能理解四次挥手的过程。TCP与UDP的区别也很好考关键是“可靠性”。TCP提供面向连接的、可靠的字节流服务有确认、重传、排序、流量控制、拥塞控制机制UDP是无连接的、尽最大努力交付的、不可靠的。选择题经常给出具体应用让你判断用了哪个协议比如视频通话为什么用UDP实时性强允许丢包而文件传输用TCP必须完整准确。HTTP部分2016年的题目已经开始关注HTTP/1.0和HTTP/1.1的区别了。其中“持久连接”是个关键概念HTTP/1.0每次请求都需要新建TCP连接HTTP/1.1默认使用持久连接可以在一个TCP连接上发送多个请求。这个知识点直到今天依然是重点。另外GET和POST的区别、状态码的含义200、301、302、404、500也要做到快速反应。3.3 数据库索引、SQL、事务特性数据库在研发工程师笔试中出现频率也很高毕竟大部分后端业务都离不开数据库。考察重点集中在索引、SQL语法和事务隔离级别。关于索引最核心的是B树索引和哈希索引的区别。B树支持范围查询和排序哈希索引只支持等值查询B树的叶子节点用链表相连方便范围扫描哈希索引没有这个概念。笔试选择题经常问“为什么数据库用B树而不是红黑树”答案是B树的节点可以存储更多索引项树高更低减少磁盘IO次数而且叶子节点链表天然支持范围查询。SQL题通常是给一张表让你写查询语句。高频考点有GROUP BY和HAVING的搭配、JOIN的类型、子查询与EXISTS的转换。有一个容易犯错的地方WHERE在GROUP BY之前过滤HAVING在GROUP BY之后过滤。如果你想筛选“某个分组内的记录满足条件”必须用HAVING而不是WHERE。这个细节每次考都有人错。事务这块ACID四个特性要能说清楚尤其是隔离级别。四个隔离级别读未提交、读已提交、可重复读、串行化以及它们各自解决的并发问题脏读、不可重复读、幻读必须一一对应。注意MySQL的默认隔离级别是“可重复读”而Oracle默认是“读已提交”。这种差异是选择题爱挖的坑。4. 实战复盘一道笔试题从审题到 AC 的完整路径4.1 一道典型的编程题题目设定与读题我拿这套题里一道很有代表性的编程题来做完整复盘。题目背景大概是给定一个整数数组和一个目标值找出数组中两个数之和等于目标值的那两个数字的下标。要求时间复杂度尽量优。这道题在今天看来已经是烂大街的经典题但在2016年的笔试现场依然有不少人卡住。有意思的是它考察的点非常全面读题是否仔细是否要求返回下标下标从0还是1开始、数据结构选型是否合理哈希表、边界处理是否到位不存在解怎么办、复杂度是否达标。如果你和我一样是“暴力流”出身第一反应可能是双重循环枚举所有数对。这个解法思路最简单但时间复杂度是O(n^2)。如果题目给出的数组长度是10^5那这个方案在执行时就非常危险。所以当我看到“数组长度可能达到10^5”这个条件时就要意识到必须用O(n)或O(n log n)的解法。4.2 从暴力解到最优解优化全过程先从暴力解法开始这一步在笔试中也可以先写出来保底保证有分。核心就是两个嵌套循环遍历所有可能的数对def two_sum_brute(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这个解法能够拿到部分分数前提是你能快速写对。但如果想要满分就必须思考如何把查找第二个数的过程从O(n)降到O(1)。答案是用哈希表记录“值-下标”的映射。遍历数组时对每个元素nums[i]检查target - nums[i]是否已经在哈希表里。如果在说明已经找到了答案如果不在把当前元素加入哈希表。def two_sum_optimized(nums, target): seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []这个解法的时间复杂度是O(n)空间复杂度是O(n)。注意我返回的下标顺序是[seen[complement], i]也就是先出现的数字下标在前。如果题目没规定输出顺序一般按这个顺序写比较自然。还有一个细节为什么不在循环开始前先把所有元素加入哈希表因为如果数组里有重复元素后加入的会覆盖先加入的下标可能在查重时出问题。边遍历边加入则避免了这个问题。这个“边遍历边建表”的手法在后续很多题目中都能复用。4.3 复杂度对比与工程取舍解法时间复杂度空间复杂度优点缺点暴力枚举O(n^2)O(1)思路简单不易出错大数据量下超时排序双指针O(n log n)O(1)空间占用小排序后下标会变需要额外处理哈希表O(n)O(n)时间最优代码简洁需要额外空间笔试时怎么选我的建议是先看题目对空间有没有限制。如果没有空间限制直接用哈希表方案因为时间最优且代码可读性最好。如果题目要求不能使用额外空间那就用排序双指针但要注意排序会打乱数组的下标这时你在返回结果前需要恢复原始下标处理起来比较繁琐。如果时间不够暴力解先提交上去拿到基础分再逐步优化。这个“先保底、再优化”的思路我在笔试现场用过很多次非常管用。另外要强调这道题还有一个变形如果题目改成“返回两个数本身而不是下标”那排序双指针就非常合适了因为不需要记录原始下标。所以遇到题目时多留个心眼同样的核心逻辑会因为输出要求不同而选择不同的解法。5. 备考方案与踩坑实录给后来人的几点实在建议5.1 从真题出发的备考路线如果你正在准备类似的研发工程师笔试我的建议是先做两三套目标公司的真题感受出题风格和难度再针对薄弱点做专项突破。具体的路线可以这样安排第一周把高频考点过一遍包括数组、链表、栈、队列、二叉树、哈希表、字符串操作每种数据结构至少能手写3道经典题。第二周重点攻克动态规划和贪心这个阶段不需要追求难题能把基础题吃透就行。第三周系统复习操作系统、网络、数据库的理论知识尤其是那些“概念对比”型的题目比如进程 vs 线程、TCP vs UDP、索引 vs 全表扫描。第四周进入模拟笔试阶段找一套历年真题严格计时3小时模拟真实环境来做。时间充裕的话还可以把力扣上的Top 100高频题刷一遍。但要记住刷题不是为了背题而是为了培养“看到题目就能想到对应算法模型”的直觉。这道题一眼看过去是DP还是双指针能快速判断比会背十个模板有用得多。5.2 笔试现场的时间分配与做题顺序我这里直接说一个经过验证的做题顺序先做编程题再做选择题最后再回头检查编程题。为什么因为编程题分值高且需要整块时间如果放在最后很容易因为时间不够而草草收场。而选择题即使放到最后也能快速蒙几个不会损失太多。编程题内部也要排优先级。如果你看到两道编程题一道看起来熟悉、一道看起来很陌生先从熟悉的那道开始做。即使题目分值相同先拿稳一题远比两题都半吊子强。我做这套题的时候第一道编程题花了20分钟第二道没头绪于是果断放弃专心检查第一道题至少保证了这道题不丢分。时间分配上我个人的经验是选择题每题不超过2分钟遇到卡壳的题目先标记跳过编程题每题控制在30分钟内。如果一道题想了10分钟还没有思路先写暴力解拿部分分然后看下一题。等所有题目做完如果有剩余时间再回头优化暴力解。5.3 常见丢分点与排查技巧看了几年笔试复盘我发现大家的丢分点其实高度一致列出来供你对照。第一编程题的代码没有处理输入为空或长度不够的边界情况。很多题目的测试用例会包含空数组、空字符串、单个元素的情况。如果代码里没有做防御性判断轻则返回错误结果重则直接抛异常整个用例得0分。第二变量名没有起好。笔试阅卷有时是人工看的如果你的代码用a、b、c这种变量名即使逻辑对了也不利于阅卷人判断你的思路反而容易在模糊评分时吃亏。第三题目要求O(1)空间你却用了额外的哈希表。这种“审题不清”的问题最可惜明明会做却因为把return nums[i]理解成return i之类的小偏差而失分。排查技巧方面我提供一个实用的办法写完代码后在脑子里或草稿纸上跑3个测试用例。第一个是“最普通的情况”验证主流程第二个是“边界情况”比如数组只有一个元素第三个是“题目给的示例”。如果你在笔试卷子上看到了类似“示例”的输入输出那就更好了——直接用它验证能至少排除一半的错误。5.4 从笔试到面谈这套题给你留下的能力延续很多人觉得笔试考完就结束了其实不是。这套题里涉及的很多思路在后续的技术面甚至实际工作中都会用到。比如双指针的思路不只是解链表题在数组算法、滑动窗口、字符串处理中到处都是。哈希表的“空间换时间”思想在工作中的缓存设计、索引优化中同样适用。至于动态规划的状态转移思想往大了说就是“把大问题分解成小问题找到子问题之间的依赖关系”这和做系统设计的思路非常相似。我个人的体会是准备笔试最忌讳“为了刷题而刷题”。每做完一道题都应该想想这个题的考点在什么场景下会出现我用的解法还有没有更好的变体如果题目加一个条件我还能不能解这种思考方式会让你从“做题的人”变成“出题的人”一旦站在出题人的角度看问题笔试的难度会降低不少。最后再分享一个小技巧笔试前一定把编程环境准备好包括编译器、常用代码模板比如快排、二分、DFS框架、输入输出模板。别小看这些准备工作很多人在笔试时因为输入输出格式不熟悉而浪费了大量时间。把这些琐碎的事情提前搞定你才能把有限的考试时间真正用在思考题目上。