2016美团研发笔试题解析：数据结构、算法与操作系统高频考点

最近重新翻出2016年美团研发工程师笔试题二越看越觉得有意思。那年头的校招笔试远没有现在这么多花活题目是真的硬核数据结构、算法、操作系统、网络、Java基础一个都跑不掉。这套题哪怕放到今天依然是一面很好的“照妖镜”能很干净地筛掉一部分只会背题的人。如果你正在准备研发岗校招或者打算跳槽去互联网大厂完全可以拿它当自测模板限时两小时做一遍看看自己到底还能不能拿得下这种老派但扎实的笔试。这篇文章我不会去逐题报答案而是从命题思路上拆把高频考点、编程题实操、答题策略和踩坑经验都过一遍。说得直白一点题目本身只是素材真正值钱的是它背后反复出现的那些底层能力要求边界意识、复杂度分析、代码落地能力。下面直接进入正题。1. 这套笔试题到底在考什么1.1 题量与题型构成2016年美团这类互联网公司的研发笔试一般还是线下笔试或者早期的在线笔试题量控制在两小时左右。整套卷子大致由三部分构成选择题、填空题、编程题。选择题覆盖面很广从Java语法、数据结构到操作系统、网络一题就是一个知识点考的是基础知识的准确度。填空题往往会让你直接写出某个程序段的运行结果或者补充某个算法的关键步骤。这种题比选择题更狠不会就是不会蒙对概率很低。编程题通常是一两道算法题需要手写完整代码。有的题目还要求写复杂度分析这一步很多人在考场上容易忽略。这种结构现在看可能觉得传统但它其实很科学。选择题考知识面填空题考推导能力编程题考代码落地能力三者缺一不可。如果你只会刷选择题不练手写代码到编程题环节大概率当场翻车。1.2 命题背后的三个隐藏逻辑第一个逻辑是考“为什么”而不是只考“是什么”。举个例子题目问“哈希表为什么能实现O(1)查找”这时候你要是只回答“因为有哈希函数”基本拿不到分。真正想听的是哈希函数如何映射、冲突如何解决、负载因子对性能的影响。这些细节才是区分“背过书”和“真懂”的分界线。第二个逻辑是考“边界意识”。选择题里经常出现数组长度、字符串长度、循环结束条件这些容易被忽略的点。比如二分查找的结束条件到底是left right还是left right边界差一个位置结果就完全不同。很多丢分不是因为不会而是因为没把边界想清楚。第三个逻辑是考“工程取舍”。同样是排序什么时候用快排、什么时候用堆排、什么时候用归并得结合数据规模、稳定性、内存开销来判断。笔试里不直接问“说说排序算法”而是给你一个具体场景让你选最合适的排序考的就是这个判断能力。2. 高频考点精讲数据结构与算法2.1 排序算法不只背时间空间复杂度排序是这套笔试题里的绝对主角。常见问法包括快速排序最坏时间复杂度是多少堆排序建堆的复杂度是多少为什么稳定排序很重要如果只是背结论很容易掉坑。先看快排。快排平均时间复杂度是O(nlogn)最坏是O(n^2)最坏情况出现在每次分区都极端不平衡的时候比如数组已经有序而pivot每次都选第一个元素。2016年的题目里就喜欢用这种场景做选择题干扰项。解决思路很简单随机化pivot或者三数取中。实际上工程里的快排不会裸写C STL的sort就是快排加插入排序的混合策略小数组直接插入排序能显著减少递归深度。再看堆排序。容易错的是建堆复杂度很多人以为是O(nlogn)其实建堆是O(n)。原因是从最后一个非叶子节点开始向下调整总调整次数加起来是一个等比数列求和结果收敛于O(n)。这个结论在选择题里很常考建议动手画一下堆结构推导一遍比死记硬背可靠。稳定排序也是一个常考点。稳定的意思是值相等的元素在排序后保持原来的相对顺序。稳定排序包括冒泡、插入、归并不稳定排序包括快排、堆排、选择排序。为什么要在意稳定性因为业务排序经常是多重排序比如先按成绩排序再按姓名排序如果第一次排序不稳定第二次排序的时候结果就乱了。2.2 链表与树的经典手写题笔试题里最经典的手写题基本绕不开链表反转、判断链表是否有环、二叉树中序遍历非递归三种。这些题看起来简单最能在短时间内暴露一个开发者的基本功。链表反转我建议准备迭代和递归两种写法。考场上优先写迭代因为不容易爆栈思路也直观。下面给一段Java迭代实现public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; }这段代码的核心是理解三个指针的推移过程。prev始终指向当前节点的前一个节点curr指向当前节点next先暂存下一个节点防止断链。每次循环把当前节点的next指向前一个节点然后整体移动。笔试时要注意最后返回的是prev不是curr因为循环结束的时候curr已经变成null了。二叉树中序遍历的非递归写法则考察栈的使用。思路是从根节点开始一路往左走把沿途节点全部压栈弹出一个节点时访问它然后把指针移到它的右子树继续往左走。这个“模拟递归”的思想在很多树相关的题里都会用到值得多练习。2.3 动态规划状态定义是关键动态规划题在当年的笔试题里一般不会出特别变态的题目但一定会有一道用来检验你有没有建立“状态”这个概念。比较常见的是最长上升子序列、编辑距离、背包问题里的简化版本。拿最长上升子序列来说很多人的第一反应是暴力枚举然后瞬间发现复杂度爆炸。正确的做法是定义dp[i]为“以第i个元素结尾的最长上升子序列长度”然后对每个i往前找所有j i且nums[j] nums[i]的位置更新dp[i] max(dp[i], dp[j] 1)。时间复杂度O(n^2)虽然不算最优但至少说明你理解动态规划的基本套路。如果你想把这道题答得更出彩还可以提一嘴O(nlogn)的贪心加二分优化维护一个tails数组表示长度为len的上升子序列的最小结尾元素然后对每个新元素在tails里做二分查找。这种“能往下挖一层”的回答在面试阶段特别加分。3. 操作系统与网络的必得分项3.1 进程线程与并发基础操作系统这块笔试里高频出现的就是进程与线程的区别、死锁的四个必要条件、进程间通信方式。这些概念非常基础但如果不做整理考场上容易答得零零散散。进程和线程的区别每家公司都喜欢考。最核心的一句话是进程是资源分配的基本单位线程是CPU调度的基本单位。进程之间内存空间相互独立线程之间共享进程的内存空间。所以线程切换成本比进程切换低但同时线程安全问题也就出现了。死锁的四个必要条件必须背得滚瓜烂熟互斥、持有并等待、不可剥夺、循环等待。考点不光是背出来还会要求你说怎么解决。思路也清晰破坏任意一个条件即可比如用锁顺序来破坏循环等待或者用超时机制让锁可以被释放。银行家算法属于更进一步的考点笔试里不一定要求写代码但至少要知道它的核心思想是“安全性检查”。进程间通信方式也是一个高频题。管道、消息队列、共享内存、信号量、Socket各自适合什么场景要能说清楚。共享内存最快因为不需要数据拷贝但需要自己用信号量做同步管道适合父子进程之间简单流式通信消息队列适合不同进程间传递结构化消息。这些优缺点对比在选择题和填空题里反复出现。3.2 TCP三次握手与可靠传输网络题里TCP三次握手和TIME_WAIT基本上是必考。三次握手的核心目的是确认双方的收发能力都正常所以不是两次也不是四次。两次握手的问题在于服务端无法确认客户端的接收能力是否正常容易导致旧连接请求残留造成资源浪费。具体过程可以这样记客户端发送SYN进入SYN_SENT状态表示请求建立连接。服务端收到后回复SYNACK进入SYN_RCVD状态表示确认了客户端的SYN同时请求客户端确认。客户端收到SYNACK后回复ACK进入ESTABLISHED状态服务端收到ACK后也进入ESTABLISHED状态。TIME_WAIT状态出现在主动关闭连接的一端需要等待2MSL。为什么非要等主要是为了保证最后一个ACK能到达对方万一ACK丢了对方重发FIN这边还能响应另外一个作用是让旧连接的所有报文在网络中自然消失避免影响新连接。TCP和UDP的区别更大题化但别小看它。只要出现“直播用TCP还是UDP”这种场景题就不仅要答UDP快、TCP可靠还要说出直播对实时性要求高TCP重传机制会导致延迟增大所以很多场景选择UDP加应用层容错。这就是从书本知识往工程实践迁移的能力。4. 编程题实操从题目到AC的完整思考4.1 题目一按数字出现频率排序这是比较典型的自定义排序题很符合2016年互联网公司的出题口味。题目可以这样描述给定一个整数数组请按照数字出现的频率从高到低排序如果频率相同则按照数字本身从小到大排序。思路不难先统计频率再排序。关键是能把“统计”和“排序”两个环节的边界处理好。统计用HashMapkey存数字value存次数。排序的时候对数组里的每个数字按它的频率和值一起比较。注意这里需要把Integer数组因为Arrays.sort支持自定义比较器但基本类型int数组不支持。Java参考实现public Integer[] frequencySort(int[] nums) { MapInteger, Integer countMap new HashMap(); for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) 1); } Integer[] boxed new Integer[nums.length]; for (int i 0; i nums.length; i) { boxed[i] nums[i]; } Arrays.sort(boxed, (a, b) - { int freqA countMap.get(a); int freqB countMap.get(b); if (freqA ! freqB) { return freqA - freqB; // 频率升序频率高的在后面所以最后集合反转或者直接降序 } return a - b; }); // 如果上面是按频率升序这里需要调整顺序 return boxed; }这里有个小细节比较容易错如果直接按频率升序排序输出结果会是频率从低到高。要实现频率高的在前可以把比较器改成freqB - freqA或者排序后反转。这种小坑在笔试里非常容易让人烦躁建议写的时候就把顺序定义清楚不要最后再靠反转补救反转又容易引入新的边界问题。写完代码后建议自己在脑子里跑一组测试用例比如nums [4, 4, 1, 2, 2, 3]统计结果是4出现2次2出现2次1出现1次3出现1次。频率相同的按大小升序所以最终结果应该是[1, 3, 2, 2, 4, 4]或[1, 3, 4, 4, 2, 2]里符合顺序的一种。手动模拟一遍能发现很多逻辑错误。如果面试官追问内存受限怎么办这时候可以改成先排序再遍历统计频率最后按频率分组输出。时间复杂度从O(nlogn)变成O(nlogn)本身没变但省掉了HashMap的开销空间复杂度从O(n)降为O(1)。虽然复杂了一些但能体现出工程思维的差异化。4.2 题目二实现LRU缓存LRULeast Recently Used缓存是2016年互联网公司笔试里的高频题美团会考不奇怪因为缓存淘汰策略在真实业务里实在太常见了。题目要求实现get和put两个操作get和put的时间复杂度都必须是O(1)。核心数据结构是HashMap加双向链表。HashMap负责O(1)查找双向链表负责维护访问顺序。每次get一个key就把对应节点移动到链表头部每次put一个新key先判断是否已存在存在就更新值并移动到头部不存在就插入头部如果容量满了就删除链表尾部节点同时删除HashMap里的对应key。Java实现要点如下class LRUCache { class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } private int capacity; private MapInteger, Node map; private Node head; private Node tail; public LRUCache(int capacity) { this.capacity capacity; map new HashMap(); head new Node(-1, -1); tail new Node(-1, -1); head.next tail; tail.prev head; } public int get(int key) { if (!map.containsKey(key)) { return -1; } Node node map.get(key); moveToHead(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { Node node map.get(key); node.value value; moveToHead(node); } else { Node node new Node(key, value); map.put(key, node); addToHead(node); if (map.size() capacity) { Node tailNode removeTail(); map.remove(tailNode.key); } } } }这段代码的关键是处理好虚拟头节点和虚拟尾节点。使用虚拟节点能省掉大量判空逻辑但也要注意removeTail的时候拿到的tail.prev一定是最后一个真实节点不会误删虚拟节点。这个细节在笔试手写时很容易出问题建议先画一画指针指向。为什么用双向链表而不是单向链表因为删除一个节点时需要知道它的前一个节点单向链表得从头遍历才能找到前驱就无法保证O(1)时间了。这个“为什么”一定要能脱口而出。4.3 题目三二分查找的边界处理二分查找看起来简单但2016年笔试题特别爱考它的变体比如查找第一个等于target的位置、最后一个小于等于target的位置、在旋转数组里找最小值。核心问题在于边界条件。先给一个稳妥的模板public int binarySearch(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这里有几个值得展开的点。第一mid写成left (right - left) / 2而不是(left right) / 2是为了避免整数溢出。虽然笔试数据未必会触发但这种写法本身就是一个加分项。第二while条件用left right意味着区间是左闭右闭每次更新left或者right都必须跳过mid否则会出现死循环。第三返回-1表示找不到但如果要找第一个大于等于target的位置返回left就行left位置天然就是插入点。旋转数组找最小值是二分查找的进阶版。题目特点原数组是非递减的然后从某个点旋转了。思路是拿nums[mid]和nums[right]比较如果nums[mid] nums[right]说明最小值在右半部分移动left否则最小值在左半部分移动right。这个题考的是对二分单调性的灵活理解值得多刷几遍。5. 答题策略与避坑指南5.1 时间分配别在选择题上恋战两小时笔试选择题加填空题一般有30到40道编程题两到三道。我见过太多人在选择题上纠结太久结果编程题没时间写这是最亏的。选择题每题分值有限但编程题一题顶十几道选择题。建议这样分配前60分钟搞定选择题和填空题不会的先标记直接跳过不要在一道题上停留超过两分钟。中间40分钟留给编程题每道题先写思路注释和框架再补细节。最后20分钟检查编译、扫一遍边界条件。如果编程题真做不完至少把核心函数骨架和主要思路写出来阅卷时还能给步骤分。还有一个容易被忽视的点笔试题册上经常会有“请在答题纸上写清楚题号”的要求在线笔试也会有代码运行按钮。实际考试时一定要留出时间确认输出格式和题目要求比如有的题要求打印结果而不是返回对象。格式不对代码再对也可能零分。5.2 剑走偏锋如何用测试用例加分很多人写完代码就交了但我当年发现一个很实用的习惯在代码注释旁边写上你设计的测试用例和预期结果或者在整个函数下面贴一段简短的main方法把边界情况跑一遍。这样做有两个好处一是让自己强制校验逻辑二是让阅卷人觉得你考虑周全。拿二分查找举例至少要测四类用例数组为空、长度为1且target存在、target不存在于数组中、target比所有数都大。这些用例能暴露大多数边界问题。如果你能在代码注释里写清楚“测试用例[1,2,3,4], target2返回1”这种说明会给面试官留下很深的印象。5.3 常见的三个丢分点主类名写错。在线笔试系统通常要求类名和文件名保持一致比如Main、Solution大小写写错直接编译失败。写完第一件事就是检查类名、方法签名和访问修饰符。数组越界。循环遍历时习惯用for (int i 0; i nums.length; i)但在删除元素、双指针、二分这种场景越界概率极高。每次更新索引前先想一想当前值是否可能等于length。忽略输入中的特殊情况。很多编程题会有“如果数组为空返回0”这种要求漏了这种判断用例跑不过。建议在写主逻辑之前先把空值、空数组、单元素分支处理掉。6. 问题排查与复盘那些年我们一起踩过的坑6.1 为什么你的快排会栈溢出笔试现场不会真让你调栈但面试的时候会被追问。快排使用递归递归深度在极端情况下会达到n也就是O(n)的栈空间数据量一大就会栈溢出。解决思路是在递归前判断如果子数组长度小于某个阈值改用插入排序或者自己维护一个栈来做非递归快排。后者更适合面试时展示你对系统栈的理解。还有一种排序场景值得注意当数据量特别大无法全部载入内存时可以使用外部排序。归并排序天然适合外部排序因为它的合并阶段可以分批读取磁盘数据。笔试如果问“内存只有100M但数据有10G怎么办”答案不是快排而是外部排序加多路归并。6.2 死锁题目答非所问怎么办看到死锁相关题目建议先写四个必要条件再写破坏条件的方法最后再谈银行家算法。这个顺序是“由浅入深”的标准范式。常见错误是直接背了“避免死锁的方法”结果题目问的是“检测死锁”答案就对不上了。如果确实不确定可以先把必要条件都列出来然后说“死锁检测可以通过资源分配图来实现检测到环路后执行恢复策略”这样至少覆盖到了检测层面的关键点比完全写偏要好。6.3 编程题编译不过的常见原因在线笔试的编译器通常比本地IDE严格很多常见问题包括导入缺失比如用了ArrayList但没import java.util.*中文字符混进代码比如注释里的分号用了中文符号变量名拼写不一致比如前面定义了len后面写成了leng编译直接报错。我的建议是手写代码或者现场输入的时候尽量在提交前把代码重新读一遍从头到尾检查符号和变量名。这个方法很笨但确实能救回不少分数。再有一个小技巧是如果在线编译器支持先编译一次再填答案能看到错误信息就不要浪费机会。整理这套题的过程中我最大的感触是2016年的研发笔试题虽然老但核心考点和现在大厂面试的重合度依然非常高。基础的数据结构、算法复杂度、操作系统和网络底层逻辑这些东西不会因为框架迭代而过时。最后再分享一个很实用的小技巧备考的时候别只刷题把每道题背后的“为什么”写在笔记里比如“为什么需要TIME_WAIT”“为什么LRU用双向链表”“为什么快排要随机化pivot”这些一句话答案比刷两百道题更值钱。拿这套题做一次全真模拟你很快就能发现自己到底是在哪个环节掉了链子。