2016年那会儿美团还是很多人眼里的“团购网站”但内部技术栈已经在往O2O大平台方向猛冲了。研发工程师的笔试算法、操作系统、网络、数据库一个都没落下题目质量放到今天来看依然很能打。我当时参加完这套笔试出来第一反应是“稳了”等结果的时候冷静下来一复盘才发现好几道题都是“看着会写出来就废”的类型。这套题二整体难度中等偏上覆盖面和考察深度都很有代表性非常适合正在准备互联网公司校招、或者想查漏补缺的研发同学拿来练手。这篇文章我就把题目逐道拆开从考察意图、解题思路到实际踩坑全部过一遍。1. 美团笔试的整体风格与考察思路先说说这套题给人的整体感觉。美团笔试向来不是那种“题库刷多了就能过”的类型它更在意你能不能把数据结构和算法用在真实的业务场景里。毕竟团购、外卖、酒旅这些业务背后全是订单、商家、用户、骑手这类高并发数据不会处理TopK、不会设计缓存、不会写聚合SQL基本就告别这家公司了。2016年的这套笔试题二题目分布大概是算法和数据结构占大头操作系统和网络各有一两道数据库和逻辑题作为补充最后还可能有一道开放性的系统设计题。整张卷子两个小时题量不算特别大但每道题都需要真思考蒙是蒙不出来的。这里有个很关键的认知笔试不是为了筛“刷题家”而是筛“能干活的人”。美团业务场景决定了他们特别看重三件事——第一基础的数据结构和算法功底扎不扎实很多业务优化最后都会落到算法问题上第二对操作系统和网络底层有没有sense线上服务出了问题能不能定位到原理层面第三能不能用工程化的思维解决问题比如缓存怎么设计、数据库怎么查才不慢。所以说这篇文章里我整理的所有题目都不是按“原题复述”的路子来写的而是按照我当时复盘后记住的核心考点和同类题型重构出来的典型版本。每道题我都会说清楚它考什么、为什么考、最优解是什么、实操中容易错在哪。这样哪怕你之后碰到原题的变形照样能应对。2. 数据结构与算法题解含代码与复杂度分析算法题是整套笔试的大头也是拉分项。这一章节我挑了几道最有代表性的题目来拆解每一道都是美团笔试里反复出现的类型在真实业务中也都用得上。2.1 数组中的第K个最大元素题目描述给定一个无序整数数组找出其中第K大的数。要求写出实现方案并分析时间复杂度。这道题考的是排序、堆和快速选择三种思路的权衡在实际业务里对应的就是“订单按金额排序取前100”“热销商品Top10”“骑手接单量排行”这类场景。先说最直观的做法——排序。直接调用排序算法排一下序然后取倒数第K个元素时间复杂度O(n log n)。大多数考生第一反应都是这个但笔试如果只写这种方案基本拿不到全分。因为美团要的是在数据规模很大的情况下依然能扛得住的方案。第二个方案是维护一个小顶堆。具体做法是维护一个大小为K的小顶堆遍历数组如果堆未满直接入堆如果堆已满且当前元素比堆顶大就弹出堆顶把当前元素入堆。遍历结束后堆顶就是第K大的元素。时间复杂度O(n log K)空间复杂度O(K)。这里的核心逻辑是小顶堆的堆顶永远是堆里最小的元素当堆里装的是“前K大”的候选者时堆顶刚好就是第K大的那个。第三个方案是快速选择。它是快排的变体每次partition后根据枢轴的位置判断第K大的数在左半部分还是右半部分只递归处理一边。平均时间复杂度O(n)最坏O(n²)但可以通过随机选取枢轴来规避最坏情况。如果让我推荐笔试时的选择先写堆方案因为代码好写、逻辑清晰、复杂度也好看快速选择可以放在后面作为加分项讨论。我当时笔试的时候写的堆方案但注释里补充了快速选择能到平均O(n)面试官后来反馈这个细节很加分。2.2 最长上升子序列题目描述给定一个无序的整数数组找到最长上升子序列的长度。例如[10, 9, 2, 5, 3, 7, 101, 18]最长上升子序列是[2, 3, 7, 101]长度为4。动态规划是美团笔试的高频考点美团从来不考那种套模板就能解的DP题一定会给你一个需要自己想状态转移的模型。最长上升子序列就是经典中的经典。最基础的DP思路是这样定义dp[i]表示以第i个元素结尾的最长上升子序列长度。对于每个i遍历它前面的所有j如果nums[j] nums[i]那dp[i]就可以从dp[j]1转移过来。状态转移方程是dp[i] max(dp[j] 1)其中0 j i且nums[j] nums[i]。时间复杂度O(n²)空间复杂度O(n)。这个思路不难但O(n²)在n10⁵的规模下会直接超时。进阶做法是用“贪心二分”把复杂度压到O(n log n)。具体做法是维护一个数组tailstails[i]表示长度为i1的上升子序列中末尾元素的最小值。遍历原数组对每个元素x在tails里用二分查找找到第一个大于等于x的位置然后替换它。如果x比tails里所有元素都大就追加到末尾。整个过程下来tails的长度就是最长上升子序列的长度。我当时第一次看到这个解法的时候愣了半天没想通为什么tails的长度就是答案。后来自己手动模拟了一遍才明白tails数组并不存储“真实的最长上升子序列”它存的是“为了后续能够接上更多元素让每个长度的子序列末尾尽可能小”的一个贪心结果。你只需要长度不用管具体序列是什么这个优化就是合法的。笔试里如果要写这道题我建议两步走先写O(n²)的DP确认正确性然后补一段二分优化的代码说明你懂更优解。这比直接甩一个二分优化上去更有说服力面试官能看出来你是在“理解”而不是“背题”。2.3 实现一个LRU缓存题目描述设计和实现一个LRU最近最少使用缓存支持get(key)和put(key, value)两个操作且在O(1)时间复杂度内完成。美团这种业务形态用户信息、商品信息、商家信息到处都是缓存场景。LRU考得非常多因为它是缓解数据库压力的核心策略之一实现起来又有不少细节。最经典的方案是“哈希表双向链表”。哈希表负责O(1)地找到节点双向链表负责维护访问顺序。每次get一个key就把对应节点移动到链表头部每次put一个新key就插入到链表头部如果容量满了就淘汰链表尾部的节点。我知道很多人会觉得用数组或者单向链表不行吗数组的移动操作是O(n)单向链表删除节点需要知道前驱节点在不知道前驱的情况下也得O(n)遍历。只有双向链表能同时满足“快速移动”和“快速删除”。这道题的代码面试时有一个高频坑很多人会忘记处理“更新已存在key”时既要更新节点的value又要移动节点位置的情况。还有一个坑是当put一个已经存在的key时不应该增加链表长度否则容量会越来越不准。如果你是在笔试限定时间内写这道题我建议把双向链表节点定义成内部类哈希表的值直接存这个节点对象这样get和put操作就不用频繁走哈希表“查了再删再插”的绕路逻辑代码会清爽很多也不容易出bug。可以说这道题是最能体现“工程代码能力”的一道算法题写得好不好面试官一眼就能看出来。3. 操作系统与计算机网络题解这部分考察的是你对“服务跑在什么上面”有没有概念。业务代码写得再漂亮底层网络一抖、内存爆了一样白搭。美团这种线上服务遇到网络抖动和资源竞争是家常便饭懂底层原理才能快速定位问题。3.1 TCP三次握手中第三次握手失败会怎样题目描述TCP建立连接时如果第三次握手客户端的ACK丢失会发生什么服务端和客户端各自处于什么状态这是计算机网络里一道相当经典的题也是我之前在笔试里最有印象的一道。看似简单的“第三次握手失败”实际上牵扯到TCP状态机、超时重传、半连接队列、全连接队列一系列知识点。先说正常流程第一次握手客户端发SYN到服务端第二次握手服务端回复SYNACK第三次握手客户端回复ACK。第三次握手完成后双方进入ESTABLISHED状态连接建立成功。但如果第三次握手的ACK丢了服务端会一直停留在SYN_RECV状态客户端却以为自己已经ESTABLISHED了。服务端在SYN_RECV状态下会启动超时重传反复重发SYNACK默认重传次数是5次不同系统参数可能不同每次重传的超时时间按指数退避增加。等到重传耗尽服务端才会放弃这个连接从SYN_RECV状态关闭连接。这个题目真正的价值在于要理解半连接队列和全连接队列的作用。服务端收到SYN后会把连接放进半连接队列等收到ACK后才会把连接从半连接队列移入全连接队列等待应用层accept。如果第三次握手ACK一直不来半连接队列就会被这种“半连接”占满导致其他正常的新连接无法建立——这就是所谓的SYN Flood攻击的基本原理。所以生产环境里如果发现连接建立变慢第一步就该去看看半连接队列是不是爆了。我在实际排查线上服务时遇到过类似的坑某个服务上游恶意重连半连接队列被打满新用户完全进不来。当时如果早一点明白“半连接队列和全连接队列是分开的”这个原理就能更快锁定故障点。所以这道题不只是在考你背三次握手的序号而是在考你有没有真的理解连接管理机制。3.2 死锁的必要条件和应对策略题目描述什么是死锁产生死锁的四个必要条件是什么如何检测、避免和解除死锁在操作系统题目里死锁几乎是必考项美团也不例外。多线程并发处理订单、资源池管理稍不注意就会踩到死锁的坑。死锁的四个必要条件是互斥条件、持有并等待条件、不可剥夺条件、循环等待条件。关键在于“四个条件同时满足才可能死锁”缺一个都不行。因此破局思路就是破坏其中一个条件这就是死锁预防的基本策略。不过实际开发中死锁预防往往得不偿失比如破坏互斥条件对很多资源来说根本不现实。更常见的做法是死锁避免最经典的就是银行家算法。银行家算法的核心思想是每次资源分配前先判断分配后系统是否还处于安全状态只有安全才分配否则等待。这个“提前判断”的思路很像你在并发编程里用锁之前先想清楚加的锁顺序是否一致。说实话笔试里能把银行家算法的流程画出来、说明白“安全序列”是什么的人不多但写出答案的人也不少。我觉得这道题真正想考察的是你后面处理线上死锁的能力。我在实际工作中排查死锁的主要手段是看线程dump用jstack把线程栈打出来找线程互相持有锁、互相等待的环路然后对照代码定位。定位到之后常用的解法是调整加锁顺序或者用tryLock加超时机制避免无限等待。如果一个考生能在笔试题里写出“死锁发生后我会用线程dump去定位”这道题的分基本就拿到了因为面试官知道你不只是背了课本概念。4. 数据库与逻辑思维题解美团是重度依赖数据库和实时分析的平台SQL能力是硬性要求。同时业务复杂逻辑思维题也会穿插考察。4.1 订单统计SQL每个用户的订单总数和总额题目描述有两张表users(id, name)和orders(id, user_id, amount, created_at)。请写出SQL查询每个用户的订单总数和订单总金额要求没有订单的用户也要展示出来订单数显示为0。这道题考察JOIN和GROUP BY的熟练程度也考察一个容易被忽略的细节——内连接和外连接的选择。最容易踩的坑就是直接写inner join结果“没有订单的用户”直接消失了。正确的做法是LEFT JOIN以users为主表把users和orders通过user_id关联然后按users.id分组用COUNT(orders.id)统计订单数用COALESCE(SUM(orders.amount), 0)处理金额为NULL的情况。写出来大概是这样的SELECT u.id, u.name, COUNT(o.id) AS order_count, COALESCE(SUM(o.amount), 0) AS total_amount FROM users u LEFT JOIN orders o ON u.id o.user_id GROUP BY u.id, u.name;这里有一个笔试题里特别爱考的细节为什么COUNT(o.id)不会把左连接产生的NULL算进去因为COUNT(列名)会自动忽略NULL值而如果写成COUNT(*)会把左连接中那些没有匹配订单的“空行”也算进结果订单数就会变成1而不是0。很多人就在这里翻车。还有一个扩展点如果订单表数据量很大直接对orders做全表聚合会慢到不可接受。实际业务中往往需要在orders表的user_id和created_at上建联合索引或者把统计任务改成离线定时计算、写入汇总表让线上查询只做读操作。面试时能主动提一嘴这种优化会让面试官觉得你不只是会写语法而是真在业务里扛过慢查询的人。4.2 烧香问题两根不均匀的香确定45分钟题目描述有两根质地不均匀的香每根从一头点燃到烧完都需要1小时。现在只给你这两根香和一个打火机如何精确确定45分钟这题是典型的逻辑思维题美团这类互联网公司很喜欢用这种“限定工具、求精确时间”的题来考思维灵活性。它的关键在于转变思路不要按“一根香烧完1小时”来用而是“同时点两头一根香就能在30分钟烧完”。做法是第一根香同时点燃两头第二根香只点燃一头。第一根香点两头30分钟烧完。此时第二根香已经烧了30分钟但因为香不均匀我们不能假设它剩余部分能烧多久只能确定它还剩“30分钟的燃烧量”——因为这根香总共能烧1小时已经烧了30分钟剩余的可燃部分相当于还需要30分钟才能烧完从单头烧的角度。在这个时间点立刻点燃第二根香的另一头那么剩余部分同时从两头烧只会花15分钟烧完。两个时间点一加第一根香烧完是30分钟第二根香从“被点两头”到烧完又过了15分钟总共就是45分钟。整个过程不需要香是均匀的因为“两头同时烧”这个操作让燃烧速度翻倍而不依赖特定位置燃烧快慢。这道题里还有一个容易误入的误区有人会想着把香截成两半或者量长度。但香是不均匀的截断之后每段烧多久根本没有保证。所以这道题告诉我们一个很朴素的道理——遇到这种限制工具的问题先想想能不能用“合起来用”的方式解锁新的时间量而不是在“一根香”的内部做文章。美团笔试里的逻辑题考的就是这种跳出固定思维的方式。4.3 系统设计题如何设计一个短URL系统题目描述请设计一个短URL系统能够让一个长链接转换成一个短链接用户访问短链接时能跳转到原始长链接。要求说明核心存储方案、跳转流程和可能的优化点。美团这类业务大量使用短链比如给用户发短信营销、App分享商品链接长URL又臭又长不转短链根本没法看。这道题考的是“从0到1”做设计的思维框架覆盖了存储、哈希、缓存、重定向、容灾多个维度。核心思路给每个长URL分配一个全局唯一ID然后把这个ID转成62进制10个数字26个小写字母26个大写字母的短字符串也就是base62编码。这样短链接的主体部分就是那个62进制字符串。存储上可以放在MySQL里表结构核心字段是id、long_url、created_atid用自增主键或者分布式发号器生成。用户访问短链接时服务器拿到短字符串反解出ID再回表查出long_url最后返回一个302重定向。这里有个设计和业务的权衡301是永久重定向浏览器会缓存结果后续访问不会再请求短链服务服务端日志拿不到完整访问数据302是临时重定向每次访问都会先经过短链服务可以记录点击量、来源等数据虽然多了一次跳转但对业务分析价值更高。美团这种需要精细化运营的公司一般会选302因为点击数据太重要了。缓存是必须考虑的热点短链会被大量访问不可能每次都打数据库至少需要一个Redis层来扛热点缓存key可以直接用短字符串value存long_url命中就直接302。另外一个容易忽视的点是短链生成的唯一性和并发问题如果用自增ID高并发下发号会冲突所以大厂一般会用分布式发号器或者预取一批ID放到内存里逐个使用。我当时笔试时把整个流程分成“发号”“存储”“跳转”“统计”四块来写每块给出一个可行方案面试的时候面试官评价是“有层次感像个做过系统的人”。系统设计题没有标准答案但思路的完整性就是分数。5. 答题策略与时间分配建议笔试不只是考你会不会还在考你在有限时间里的决策能力。这套卷子我复盘的时候就在想如果时间重来一次我会怎么分配时间。先说一个核心策略先做会做的再做能努努力的最后再啃硬骨头。别一上来就和某道算法题死磕死磕20分钟换不出一道AC后面该拿的分全丢了。我的习惯是拿到卷子先花2分钟扫一遍所有题目给题目难度分个档送分题比如SQL、逻辑题、常规题比如LRU、堆TopK、硬核题比如快速选择优化、系统设计。然后先花10到15分钟把送分题完整拿到手再攻常规题硬核题最后有时间再做。时间分配上如果总时长是120分钟我建议按这道套题的题型配比来分算法题约50分钟每道控制在15分钟左右操作系统和网络约25分钟数据库、逻辑和系统设计约30分钟最后留15分钟检查边界情况——数组为空、链表只有一个节点、数据量极大、整数溢出这些都是美团笔试里非常爱埋的隐藏分。还有一个特别重要的应试技巧不会做的题也要写思路。写代码之前先用文字描述你的思路哪怕是“这题我想到用优先队列解但边界条件还没想清楚”阅卷人至少能看出你有分析能力而不是瞎写一通。美团笔试阅卷很看思考过程有时候一段清晰的思路比一段跑不起来的代码更值钱。时间管理还有一个反面教训我身边有同学在“数组第K大”这道题上用了快速选择然后被最坏情况O(n²)的证明卡住了纠结了半小时后面简单题都没时间做。笔试是争取总分的过程不是证明自己“什么都会”的过程。适度取舍才是聪明人的打法。6. 笔试中的常见坑与独家避坑技巧做了这么多年技术也在面试官的位置上看过不少笔试答卷来整理一下这套题里最常见的几个坑以及我自己的应对方法。第一个坑LRU缓存只写了哈希表没有双向链表。很多人觉得用LinkedHashMap一行就搞定了但笔试要求手写原理你必须展示出“为什么LinkedHashMap能实现LRU”的内部逻辑。我的做法是先画一个双向链表的结构草图标注头尾指针和哈希表的映射关系再开始写代码。草图一出来思路就顺了。第二个坑SQL里COUNT用错了。前面提到过COUNT(*)会把LEFT JOIN产生的NULL统计进去。这个坑非常隐蔽因为我见过很多工作两三年的开发也会犯。避坑技巧是写聚合SQL时先想一下“如果关联字段是NULL我这行统计会变成什么”。把所有NULL的情况在脑子里过一遍很多坑就自动浮现了。第三个坑系统设计题只写方案不写理由。比如设计的短URL系统只说了“用301跳转”没说为什么不用302只说了“用MySQL存”没说为什么还要加Redis。美团这类公司招人最重要的是“会做决策的人”——你选了这个方案必须说清楚背后的取舍。我在写系统设计题时养成了一个习惯每个关键选择后面都用括号标注“原因XXX”这既是提醒自己也是向阅卷人展示思考过程。第四个坑死锁题目只写了四个条件没写排查方法。这在前面已经说过了更重要的是笔试最后如果有机会写“我会用什么工具去定位死锁”这一句含金量极高因为它说明你有实战思维。每个操作系统考点都尽量往实战靠一点点而不是纯背书。回过头来看这套美团2016研发工程师笔试题二给我最大的收获并不是具体的算法题怎么做而是它让我意识到大厂笔试考的不只是知识存量更是你在限制条件下做决策的能力。数据结构要选最合适的、跳转要选有业务价值的、SQL要选能防NULL的——每一个选择背后都是工程思维的体现。最后再分享一个我后来常用的小技巧准备笔试的时候不要光刷题拿到一套题先自己给自己讲一遍“这题在业务里什么地方会用上”。讲得出来说明你真的懂了讲不出来哪怕AC了也是背题。美团这套题恰恰每一道都能在真实的业务场景里找到它存在的理由。能把这些理由想透笔试通过只是起点后面面试里的系统设计、项目深挖你都会比别人多一分底气。