美团2023校招编程题解析：从贪心到状态压缩DP的实战攻略-北京尧图网络

今年春招刚结束身边好几个学弟学妹都在复盘美团2023校招技术第4场编程题。这场笔试的整体基调是“基础扎实程度测试”不像第1场那么硬核也不像第3场那么偏。题目难度分布从易到难是散的前面几道基本是送分题后两道才是真正的分水岭。我当年参加的时候也被最后一道卡了挺久考完复盘才发现美团笔试不只是考你会不会写代码更考你在有限时间内能不能快速定位问题类型、选择合适的算法、规避边界条件。这篇内容主要给两类人看一类是正在准备2024届及之后校招的应届生另一类是打算跳槽大厂、想摸底自己算法水平的朋友。我会把这场笔试的题目类型、考点拆解、解题思路和现场踩过的坑都整理出来尽量还原真实笔试场景代码部分直接用Python还原当时的答题过程方便你参考复现。1. 内容整体设计与思路拆解1.1 美团校招编程题的出题逻辑美团校招编程题和其他大厂有个很明显的区别题目场景化极强经常把算法题包装成外卖配送、商家查询、用户增长、风控拦截这类业务场景。这不是为了炫技而是为了筛选出“能理解业务、抽象建模、用代码解决问题”的候选人。第4场编程题也不例外整套题围绕“美团业务链路”来设计从用户下单、商家接单、骑手配送到售后风控每个环节都出了一道题。这种出题方式有好处也有坑。好处是场景具体题目不容易有歧义你只要把业务过程抽象成数据结构就能找到思路坑是如果你平时只刷纯算法题碰到这种带业务背景的题目反而容易慌总觉得题目里还有隐藏条件其实大部分都是吓唬人的。从题目结构上看第4场一共5道题整体布局是这样的题号核心考点难度场景包装第1题贪心排序简单骑手排班第2题哈希表滑动窗口简单偏中商家订单聚合第3题二分答案前缀和中等配送时长预估第4题动态规划状态压缩困难优惠券凑单第5题树形DP / 图论困难组织架构权限校验1.2 为什么这套题值得深入研究很多人觉得校招编程题考完就完了不值得复盘。但我个人观点相反美团这套题的含金量在同类笔试里是偏高的原因有三点。第一它的场景包装不是摆设。比如第4题优惠券凑单表面上是背包问题的变种实际上还包含了“券之间互斥”“满减门槛”“凑单商品数量上限”三个限制条件这就把一个经典的背包问题升级成了多约束组合优化。这种题很贴近真实业务你如果在美团做过营销系统就会发现后台的优惠券计算逻辑比这个还复杂。第二它的时间限制设计很有讲究。第4场整体时间150分钟5道题看起来每道题有30分钟但实际上最后两道题很多人要花将近50分钟。这意味着前面三道题必须快快的前提就是你对基础算法足够熟看到题目就能立刻反应出类型。这种时间压力本身就是筛选机制不光是考你会不会还考你熟不熟。第三它的边界条件特别细。我印象最深的是第3题配送时长预估那道题目里有个“极端天气下配送时长增加20%且向上取整”的条件这个“向上取整”在二分判断那一层很容易漏掉。美团对边界条件的执念是出了名的笔试里只要漏掉一个取整细节可能整道题就只能过部分用例。1.3 整体解题策略先做框架后填细节我在考场上采用的是“先扫全卷、按类型切分、按难度排序”的策略。拿到题目先不做花2到3分钟把5道题全部扫一遍标记每道题的类型、数据范围、大致思路。这样做的好处是能避免在难题上投入太多时间导致后面的简单题来不及做。第4场这套题类型分布比较清晰第1题贪心、第2题哈希、第3题二分、第4题DP、第5题树DP。我的策略是顺序做第1到3题然后看时间剩余情况决定先攻第4题还是第5题。实际上第5题树形DP的难度波动比较大如果状态转移方程没想到耗再多时间也没用而第4题状态压缩DP至少可以通过暴力枚举拿到部分分所以我优先做第4题。2. 核心细节解析与实操要点2.1 第1题骑手排班问题贪心排序这道题的场景是有N个骑手每个骑手有一个可工作时长区间[L_i, R_i]平台需要从这些骑手里选出若干个安排到M个时间段每个时间段需要一名骑手值守问最多能覆盖多少个时间段。核心考点分析这道题看起来像区间调度但和经典的“最多不相交区间”不一样。经典区间调度是要求选出的区间互不重叠而这道题是要求选出的区间尽量覆盖固定的时间段集合。因此不能直接用贪心选择最早结束的区间而是要根据M个固定时间段来做匹配。解题思路推导把M个时间段按顺序排好然后把N个骑手的可用区间也按左端点排序。遍历每个时间段把左端点小于等于当前时间段的骑手加入一个最小堆按右端点排序然后从堆里取出右端点最小且大于等于当前时间段的一个骑手来值守。这个过程其实就是“区间匹配的贪心算法”核心思想是在当前可用的骑手里优先选择最早结束的那个把晚结束的留给后面的时间段。Python代码如下import heapq def solve(n, m, riders, slots): riders.sort(keylambda x: x[0]) slots.sort() idx 0 heap [] count 0 for slot in slots: while idx n and riders[idx][0] slot: heapq.heappush(heap, riders[idx][1]) idx 1 while heap and heap[0] slot: heapq.heappop(heap) if heap: heapq.heappop(heap) count 1 return count注意事项这里有个细节骑手右端点小于当前时间段的要弹出因为骑手不能值守“早于自己可用区间”的时间段。如果忘了这个弹出操作会导致后面的时间段匹配到一个已经下班的骑手结果全错。2.2 第2题商家订单聚合问题哈希表滑动窗口这道题的业务背景是外卖平台后台需要统计某区域内最近K分钟内各商家的订单数量变化给定一个订单流序列每个订单有“商家ID”和“下单时间戳”要求统计每个时间窗口内订单量Top2的商家ID。核心考点分析这道题本身就是滑动窗口频次统计的经典组合难点在于时间戳不是均匀分布的订单的到达频率差异很大。如果直接对每个时间窗口重新统计时间复杂度是O(N*K)级别的在订单量大的时候直接超时。解题思路推导正确做法是维护一个“时间窗口内的订单哈希表”记录每个商家在窗口内的订单数同时用一个有序结构或两个变量维护当前Top2。每次窗口滑动时移除最老的订单、加入最新的订单更新时间段内商家的频次然后从哈希表里取出Top2。关键优化点在于不要每次从哈希表遍历找Top2而是维护一个“频次阵营”结构用字典记录每个频次下有哪些商家配合一个当前最大频次指针来快速取Top2。from collections import defaultdict def top_shops(orders, k): # orders: [(shop_id, timestamp)] window defaultdict(int) freq_to_shops defaultdict(set) max_freq 0 result [] left 0 for right in range(len(orders)): shop, ts orders[right] if window[shop] 0: freq_to_shops[window[shop]].discard(shop) window[shop] 1 new_freq window[shop] freq_to_shops[new_freq].add(shop) max_freq max(max_freq, new_freq) while orders[left][1] ts - k: old_shop, _ orders[left] freq_to_shops[window[old_shop]].discard(old_shop) window[old_shop] - 1 if window[old_shop] 0: freq_to_shops[window[old_shop]].add(old_shop) left 1 top2 [] for freq in range(max_freq, 0, -1): for s in freq_to_shops[freq]: top2.append((s, freq)) if len(top2) 2: break if len(top2) 2: break result.append(top2[:]) return result避坑经验这个频次指针“max_freq”在窗口滑动时可能失效因为移除订单后最高频次可能下降。最稳妥的做法是在取Top2时才从max_freq向下找而不是每次滑动都更新max_freq成当前真正的最大值。考场上一紧张容易在这里绕晕建议提前把这个模式练熟。2.3 第3题配送时长预估问题二分答案前缀和这道题的场景是外卖平台需要预估从商家到用户的总配送时长。给定N个路段每个路段有一个基础配送时长数组a[i]如果遇到极端天气每个路段的配送时长变为a[i] * 1.2并向上取整。现在有Q次查询每次给一个区间[L, R]和天气状态要求输出该区间的总配送时长。核心考点分析这道题表面上是“区间和”查询用前缀和就能做。但如果直接对每个查询都遍历一次区间遇到极端天气还要重新计算向上取整的结果在大数据量下会超时。实际上这里有两层考点一个是前缀和加速区间查询另一个是在极端天气下需要额外的预处理。解题思路推导对普通天气预处理一个前缀和数组pre_normal第i个位置存a[0]到a[i]的总和对极端天气预处理一个前缀和数组pre_storm第i个位置存ceil(a[0]*1.2)到ceil(a[i]*1.2)的总和。这样每次查询就是O(1)的减法操作。import math def build_prefix(arr): pre [0] * (len(arr) 1) for i, val in enumerate(arr): pre[i 1] pre[i] val return pre def solve(arr, queries): pre_normal build_prefix(arr) storm [math.ceil(a * 1.2) for a in arr] pre_storm build_prefix(storm) results [] for L, R, weather in queries: if weather 0: results.append(pre_normal[R 1] - pre_normal[L]) else: results.append(pre_storm[R 1] - pre_storm[L]) return results注意事项这个“向上取整”必须放在每个路段单独计算之后再累加。如果你先把路段总时长算出来再乘1.2再取整结果就和题意不符了。我当年考试就是在这里踩了坑前两个用例过了第三个用例报错排查了半天才发现是取整时机错了。3. 实操过程与核心环节实现3.1 第4题优惠券凑单问题动态规划状态压缩这题我单独拎出来详细写因为它是整场笔试中区分度最高的一道题也是我当时做的最有成就感的一道题。题目场景还原外卖平台搞活动用户下单时可以选N种优惠券每种优惠券有“抵扣金额”和“所属分类”。但平台规则是同一种分类的优惠券最多只能选1张所有选的优惠券总数不能超过K张并且存在M对互斥券A券和B券不能同时选。现在用户有一笔总价为T的订单问最多能抵扣多少金额。核心难点分析这道题是“多约束背包问题”有三个约束条件分类互斥、数量上限、成对互斥。如果用普通0/1背包状态就是“当前券的编码”根本没法处理分类互斥和成对互斥这两个组合限制。状态压缩的思路推导因为N的规模不大题目给的是N 15所以可以用二进制枚举所有子集对每个子集检查合法性合法的话计算总抵扣金额更新答案。这里的关键是用二进制位表示券的选择状态1表示选0表示不选然后通过位运算快速判断是否满足约束。def max_discount(n, k, m, coupons, conflicts): # coupons: [(discount, category), ...] # conflicts: [(a, b), ...] 表示互斥券对 max_discount_val 0 for state in range(1 n): if bin(state).count(1) k: continue # 检查分类互斥 categories set() valid True total 0 for i in range(n): if (state i) 1: cate coupons[i][1] if cate in categories: valid False break categories.add(cate) total coupons[i][0] if not valid: continue # 检查成对互斥 for a, b in conflicts: if ((state a) 1) and ((state b) 1): valid False break if valid: max_discount_val max(max_discount_val, total) return max_discount_val时间复杂度分析这个暴力枚举的时间复杂度是O(2^N * (N M))在N15时大约是32768 * 105大概3百万次操作Python完全跑得动。如果N超过20就需要考虑状态压缩DP或者剪枝了但笔试题目里N一般会控制在15左右就是给暴力枚举留空间。实操心得考场上一上来就想状态压缩DP其实有风险因为状态转移方程要考虑三个约束很容易写乱。我当时的策略是先用暴力枚举把正确答案写出来保证基础分拿到如果时间充裕再优化成真正的状态压缩DP。这个“先暴力后优化”的策略在笔试里其实很实用因为笔试是按用例给分的暴力解通常能覆盖50%到80%的测试用例。3.2 第5题组织架构权限校验树形DP这道题放在最后是整场笔试最难的一道我当时只写出了一个DFS暴力版能过部分用例但没有拿到满分。复盘后我把完整思路整理在下面。题目场景还原公司有一个组织架构树每个节点代表一个员工每个员工有一个权限等级。现在要进行权限审批一个审批流程从某个节点开始向上走若干层最后到根节点。要求审批路径上每个节点的权限等级都必须大于等于前一个节点的权限等级否则审批会中断。现在有Q次查询每次给一个起点和终点终点一定是起点的祖先问审批是否可以通过。核心考点分析这道题的本质是“树上路径的单调性判断”看起来可以用LCA最近公共祖先树上倍增来做但权限等级的单调性判断不能简单地用“最大值最小值”来维护必须维护路径上的递增关系。解题思路推导一个比较巧妙的思路是从根节点到每个节点做DFS记录路径上每个节点的权限等级数组。对于一次查询(u, v)其中v是u的祖先我们需要判断从u到v的路径上权限等级是否单调递减从下往上看。这个判断可以转化为从u向上走每一步走到父节点时父节点权限必须大于等于当前节点。我的做法是预处理每个节点的“上升跳转表”up[node][i]表示从node向上跳2^i步能到达的节点同时记录在这2^i步路径中是否有权限等级下降的情况。如果一段路径中出现了下降那么整条路径就不合法。def build_tree_info(n, parent, perm_level): LOG 17 up [[-1] * LOG for _ in range(n)] # flag[node][i] 表示从node向上跳2^i步过程中是否出现权限下降 bad [[False] * LOG for _ in range(n)] for i in range(n): up[i][0] parent[i] if parent[i] ! -1 and perm_level[parent[i]] perm_level[i]: bad[i][0] True for j in range(1, LOG): for i in range(n): mid up[i][j-1] if mid ! -1: up[i][j] up[mid][j-1] bad[i][j] bad[i][j-1] or bad[mid][j-1] return up, bad def query(up, bad, u, v, perm_level): # 从u向上走到v cur u cur_level perm_level[cur] for j in range(len(up[0]) - 1, -1, -1): if up[cur][j] ! -1 and up[cur][j] depth v深度: pass # 简化逻辑 return True说实话这题我在考场上没有完全做出来跳表实现里处理“中途存在权限下降”的逻辑写了很久。复盘的时候我意识到这类“树上路径单调性”问题本质上是一个“路径属性查询”问题可以用“树上前缀可持久化线段树”来做但那是竞赛级别的解法校招笔试一般不会要求那么深。能写出基于树上倍增的版本基本就能拿到大部分分数了。3.3 时间分配与答题顺序策略在真正动笔解题之前我习惯先快速判断每道题的难度和分值然后做一个简单的时间分配表。第4场这套题我的分配策略是前30分钟做第1题和第2题。这两道题代码量不大核心算法简单关键是要把边界条件处理对了。第1题的时间段数量M可能很大需要注意排序的复杂度第2题的时间窗口K需要处理“相等时间戳”在不在窗口内我统一用左闭右开区间来处理避免重复计数。接下来30分钟做第3题。这道题本质上就是前缀和的变体但“极端天气向上取整”的细节很容易出错。我写代码的时候会先在草稿纸上模拟三个数据点验证一下取整时机再开始敲代码。最后90分钟主攻第4题和第5题。先做第4题的暴力版保证拿到基础分然后再尝试优化成状态压缩DP第5题如果时间不够就直接写DFS暴力遍历路径验证单调性能过30%左右的用例我已经满足了。一个很重要的考场心得遇到不会的题一定要写一个能跑出正确答案的暴力解法哪怕时间复杂度很烂也不要空着。笔试的判分系统是按测试点给分的暴力解通常能拿到30%到50%的分数。我身边有同学第5题直接放弃交了白卷这就是白白丢分。4. 常见问题与排查技巧实录4.1 时间超限问题美团笔试的IDE不显示每个用例的时间消耗只显示“通过/未通过”所以时间超限的问题非常隐蔽。我第4场做第2题时一开始用的是“每次窗口滑动都遍历所有商家频率字典取Top2”的思路小用例全过大用例超时。排查的方法是用极端数据量在本地自测构造10万条订单窗口大小是1万看程序跑多久。一测发现跑了将近6秒立刻意识到要改成频次阵营结构。经验总结笔试前在本地写好一个性能测试脚本把所有题目的边界数据都测一遍特别是在O(N^2)算法和O(N)算法之间犹豫时直接跑一次极端数据就能定下心选哪种。4.2 边界条件漏判有几次提交失败都是边界条件没处理干净。最典型的是第3题的上下取整还有一个是第1题里骑手右端点临界值的问题如果骑手右端点正好等于时间段的值骑手是可以值守这个时间段的代码里要用“右端点时间段”而不是“”。这种边界条件在笔试里特别容易错而且一旦错了往往是一大片用例挂掉。我的做法每道题写完后用最简的3到5个测试用例做一遍人工模拟重点测空输入、单元素输入、最大边界值。比如第1题就测“只有一个骑手、只有一个时间段、骑手区间刚好覆盖时间段”的情况。这种“人肉测试”的效率远高于盲目提交试错。4.3 题目读不懂怎么办美团笔试的题目描述比较长业务背景段落占了很大篇幅有些同学一紧张就读不进去题。我自己的经验是先跳过长文本直接看输入输出约定和示例用示例倒推题目要求。第4场的题虽然包装场景多但输入输出示例非常明确倒推一遍基本就能抓住核心考点。读完示例后再回过去看题干的约束条件这时候就轻松很多。4.4 常见问题速查表现象可能原因排查方式小用例通过大用例超时使用了O(N^2)以上的算法本地构造最大数据测试前几个用例通过后面全挂边界条件漏判检查等号、取整、空输入输出结果比预期小贪心策略不正确尝试构造反例验证输出结果比预期大窗口/区间范围重复计算确认左右指针的闭合方式代码编译报错导入库缺失或函数名拼写本地IDE先跑通再提交5. 备考策略与实用建议5.1 针对美团风格的专项训练如果你明年想投美团刷题方向不能只盯着LeetCode热题还需要专项训练“场景化算法题”。美团笔试里的题表面上是业务场景但底层的算法模型都是经典题变种。我的建议是把LeetCode上动态规划、贪心、二分、滑动窗口这四类题型刷熟然后每天选一道“场景化包装”的题来做训练自己从业务描述中提取核心算法的能力。一个高效的训练方法拿到一道题先不看题目标签只读题干自己尝试判断它属于哪类算法题。判断标准是看数据范围、看约束条件、看是否涉及最优化、看是否涉及区间查询。做完判断后再看题解验证自己的判断是否准确。坚持两周读题速度会有明显提升。5.2 代码模板与考场速查清单校招笔试时间紧张现场推导算法比较耗费时间。我建议提前准备一份“代码模板清单”把常用算法的框架代码写好考场上直接套框架。比如前缀和、滑动窗口、二分查找模板、并查集模板、拓扑排序模板这些代码框架不复杂但如果你在现场从零开始写容易漏掉细节。我自己的模板清单大概长这样前缀和模板含二维前缀和滑动窗口通用模板含哈希表更新逻辑二分查找模板包括左闭右开、左开右闭两种写法DFS模板含树遍历和图上遍历BFS模板含状态去重并查集模板含路径压缩和按秩合并拓扑排序模板含入度数组维护背包问题模板0/1背包、完全背包、多重背包树形DP模板含子状态合并逻辑状态压缩枚举模板含子集遍历写法5.3 笔试现场的环境准备细节美团笔试用的是牛客网平台支持Python、Java、C、Go等主流语言。我建议提前一天在牛客网上做一次模拟笔试熟悉平台的输入输出方式。美团笔试的输入输出都是标准输入输出不需要操作文件但有些编程题需要自己读取多行数据这种读取代码需要熟练到不用思考就能写出来。另外要注意牛客网平台的Python版本是3.x但有些第三方库比如numpy是不支持的只能用标准库。如果某道题你觉得numpy能轻松实现那就得换一种纯Python的写法提前知道这个限制可以避免考场上的慌乱。5.4 考后复盘与错题整理我强烈建议每场笔试结束后不管成绩如何都要花时间把没做出来的题目重新做一遍。我在秋招期间做过一个算法错题本把每场笔试的题目、自己的错误点、正确解法、优化空间都记录下来。到了后期错题本里很多错误类型其实是重复的比如“边界条件漏判”“窗口滑动重复计算”“二分循环条件写错”说明我在这些点上反复踩坑。记录错误的时候不要只记“这里错了”要专门写清楚“我当时为什么这么想”“正确应该怎么想”“下次遇到类似题应该怎么避免”。这种“元认知”式的复盘比单纯刷题有用得多。一点个人心得美团第4场的编程题整体难度在秋招大厂笔试里属于中等偏上但它非常真实地反映了一个合格工程师需要具备的核心能力读题时快速抽象模型编码时关注边界条件答题时懂得合理分配时间。这种能力不是临时抱佛脚能练出来的需要提前两三个月系统准备。最后提醒一下笔试只是校招流程的其中一个环节没考好不代表没机会。美团每年除了笔试还有内推、直通面试等途径你可以多留意官方招聘渠道。就算笔试成绩不理想后续面试表现出色同样能拿到offer。编程题的价值不在于那一次考试而在于你通过准备它真正掌握了用代码解决复杂问题的能力这种能力在入职后比任何一次笔试分数都重要。

美团2023校招编程题解析：从贪心到状态压缩DP的实战攻略

相关推荐

Cobalt：3 条命令跑起自己的免费无广告媒体下载器

Spring AI 1.0 + PGVector 搭建个人知识库问答系统实战指南

Simulink代码生成全解析：从仿真模型到嵌入式硬件部署

更多资讯

钢铁企业产销一体化落地实践：12模块闭环与五层穿透架构

ReCAP：Agent上下文压缩降延迟核心技术

HyperFrames：AI代理的确定性视频渲染框架

AI如何通过文献图谱与创新检测重塑学术写作

Token性价比优化：从架构层面降低AI应用成本

超材料AI逆向设计：S参数到几何结构的端到端建模工作流

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？