2017滴滴秋招笔试编程题剖析：算法考点与实战策略

2017年秋招季滴滴出行的笔试编程题在牛客网上一度是讨论热点。那会儿流传最广的一句话是想进滴滴先过算法关。和其他大厂动辄考察一整套算法体系的题风不同滴滴的编程题和出行业务咬得很紧——地图、路径、订单、派单、拼车这些关键词几乎就是题型的风向标。这篇文章不打算把每道题都罗列一遍那没有意义我想做的事是把这套题背后真正考察的东西拆开考了什么算法为什么考这些限时作答时怎么下笔以及今天的你还能从这套旧题里带走什么。1. 2017年滴滴秋招笔试考什么线上平台、出题风格与业务基因1.1 线上笔试的基本盘平台、时长与题量2017年滴滴的秋招笔试大多在牛客网等在线评测平台上进行Java、C、Python都能选时间一般控制在90分钟到120分钟之间。编程题通常3到4道题量不算大但不少人在后半段都会出现写不完的情况——不是因为题量而是因为前几题耗了太多时间在理解和建模上。这个问题直到今天依然存在所以我等下会专门用一章讲限时实战策略。不同岗位的题有明显侧重。研发岗的编程题更看重编码实现能力数据规模通常给到10^5级别要求你必须写出复杂度正确的算法纯暴力基本过不了隐藏用例算法岗的题则更偏模型设计和推导有些题甚至允许你先把思路写清楚再写代码但代码必须能跑通公开用例测试开发岗偶尔还会混入一道与测试相关的逻辑题比如设计用例覆盖某个路径组合。如果你投的是研发岗却按算法岗的重思路、轻实现来准备笔试现场很容易吃亏。这里有个容易被忽略的信息2017年是出行行业竞争最激烈的年份之一滴滴校招简历池非常大笔试通过率一直不高。这意味着编程题必须足够有区分度——既不能难到没人做得出来也不能简单到大家都会。所以你看到的题往往是场景复杂、算法中等题目描述动辄几百字先铺一段业务背景再抽象成算法问题。1.2 为什么滴滴的编程题业务味这么浓滴滴笔试最鲜明的特点就是业务味浓。为什么会这样因为出行领域本身就是一个巨大的算法试验场。用户发单后系统要在几十毫秒内决定派给哪个司机这是一个多约束的实时匹配问题司机接驾要经过哪条路这是一个标准的最短路问题多个人拼车如何规划上下车顺序这是一个组合优化问题。笔试题目从这些业务场景里抽取一个简化版考察的就不仅是你会不会背算法模板而是你能不能把一个模糊的业务问题翻译成清晰的算法问题。这种建模能力恰恰是工程岗和算法岗在实际工作中最需要的能力。你可以在笔试中不会KMP可以写不清线段树的标记下传但如果你能把一个高峰期大量乘客同时等车系统如何保证较短的接驾时间的长篇描述快速拆解成排序双指针或者二分答案贪心校验的算法模型那么你已经领先了很大一批人。所以在看这套题的时候不要只盯着算法本身。要习惯先读业务背景再找关键约束最后才去想算法。这也是我反复强调的滴滴的题题目描述里每句话都有用每句话都可能对应一个坑。2. 高频考点的算法内核图论、动态规划、贪心如何对应出行场景2.1 图论与最短路从司机接驾路程抽象出的核心考点如果要把滴滴历年笔试的考点排个序图论一定在最前面。原因不需要多想滴滴的核心业务就是地图和路径。一道典型的题会这样出给出一个城市地图以点和边的方式给出道路网络再给出若干司机的位置和乘客的上车点求每个司机到乘客的最短接驾时间。这里的核心考点是单源最短路。数据规模不大时比如节点数几百直接用Dijkstra就能过节点数上万但边是稀疏的就要用堆优化的Dijkstra复杂度O(E log V)。如果地图存在负权边——笔试里一般不考但如果考了就要SPFA或Bellman-Ford。如果要求的是所有节点之间的最短路并且节点数少那就用Floyd。我见过不少人在最短路题上翻车原因不是不会Dijkstra而是读题不仔细。题目给出的边可能是有向的可能是双向的可能存在多条边起点的编号可能是0也可能是1。这些细节不处理好算法再熟也白搭。2017年滴滴就有过一道跟地铁换乘有关的题本质上是最短路但很多人在建图时漏了换乘站这个关键抽象——你要建的是站-线网络而不是简单的站-站网络。用一张表来整理最短路算法的选型笔试现场可以直接参考场景推荐算法时间复杂度数据规模上限单源、非负权边堆优化DijkstraO(E log V)V、E到10^5单源、可能有负权边SPFA / Bellman-FordO(VE) 最坏V ≤ 1000多源多汇、节点少FloydO(V^3)V ≤ 500无权图、求步数BFSO(V E)V、E到10^5这个表适合贴在电脑旁边刷题时反复对照。当你把求最短接驾时间这类题做熟了以后看到求最少换乘次数求最早到达时间都能快速对应到图论模型。2.2 动态规划从计费组合到资源分配的通用解法动态规划在滴滴的题里也常出现但出现的方式非常业务拼车费用的分摊方案、多个优惠券叠加时的最优组合、一段行程中如何分配司乘人数以获得最大收益。包装不同内核都是DP。做这类题的关键是找出状态定义和转移方程。以优惠券组合为例假设有n张优惠券每张有面值和适用条件要在预算范围内凑出一个最优的抵扣方案这就是一个典型的背包DP。状态dp[i][j]表示前i张优惠券在已用金额为j时的最大抵扣额转移就是用或不用的二选一。DP的难点其实不在转移方程本身而在于你能不能识别出这是一道DP题。很多人被题目的场景描述带偏绕着弯去想贪心或搜索结果时间全耗进去了。我的经验是题目里出现最大/最小方案数组合最优这类关键词同时数据范围不超过10^5但又不适合排序贪心的时候往DP方向想大概率没错。再提一点DP题在笔试中经常以小数据规模出现因为DP的正确性很难通过几个用例证明出题人需要靠隐藏用例来筛掉半懂不懂的候选人。所以DP题的得分率往往偏低。我的建议是先熟练经典的最长公共子序列0-1背包区间合并三类DP再去看那些复杂的业务包装题会顺手很多。2.3 贪心与排序派单匹配问题的高性价比解法贪心是性价比最高的算法类型——代码短、思路快、容易得分。滴滴的派单匹配题就经常用贪心解决。典型模型多个司机在线每个司机从当前位置到乘客上车点的时间不同多个乘客在等待每个乘客能接受的最大等待时间不同。系统需要在所有可能的匹配中让尽可能多的订单成功成交。这类题的通用解法是排序加贪心。先把司机按接驾时间排序乘客按最大等待时间排序然后逐对匹配。贪心的正确性在于一个接驾时间短的司机如果连等待时间上限最小的乘客都满足不了那它去接其他乘客更不可能反过来一个等待时间上限大的乘客用接驾时间短的司机去接总不会比用慢司机去接更差。有了这个逻辑排序后一趟扫描就能得到最优匹配。但这里也要提醒一句贪心不是万能钥匙。笔试里经常出看着像贪心、实际要DP或者网络流才能做的题。判断标准是贪心要求每一步的局部最优选择不会影响后续的全局最优如果没有这个性质就别硬贪。举个例子如果每个司机接单后还要花时间送乘客去目的地那么接驾时间最短优先就不再是最优策略因为一个司机可能因为接了一个近单而错过一个更远但收益更高的订单。这种问题就要换思路了。我在第3章会拿一道模拟题完整演示一遍贪心从思考到验证的过程。3. 一道模拟派单题从暴力到最优完整推导与Python实现3.1 题目设定与输入输出约定为了把这类题的完整思考过程讲透我设计了一道与当年真题风格高度一致的模拟题考点、数据规模、题目包装都按滴滴2017年秋招的标准来。真题的原题细节现在已经不好考证但这种司机-乘客匹配模型是那一批题目里反复出现的骨架。题目背景某区域内有n位司机和m位乘客同时出现在系统里。每位司机有一个接驾耗时s[i]表示从当前位置到乘客上车点的最短时间每位乘客有一个等待上限t[j]超过这个时间乘客就会取消订单。如果s[i] t[j]则司机i可以服务乘客j。每个司机只能服务一位乘客每个乘客也只能被一位司机服务。请问系统最多能成功匹配多少对司乘输入格式第一行两个整数n, m第二行n个整数s[1..n]第三行m个整数t[1..m]。所有数值在1到10^9之间n和m都在1到10^5。输出格式一个整数表示最大匹配数。这道题的难点在于n和m都是10^5不可能用O(n*m)遍历所有组合同时数值范围到10^9可能出现很大的输入算法要与数值无关。3.2 为什么选择贪心而不是匈牙利算法我的第一反应不是直接写匈牙利算法——虽然这道题看起来像二分图最大匹配。原因是匈牙利算法的复杂度在O(n*m)级别在10^5的数据规模下肯定会超时而且它的编程实现比贪心复杂得多笔试里一旦写挂连改的机会都没有。选贪心是因为这道题的匹配关系具有特殊的单调性司机接驾时间s[i]是单调排列的乘客等待上限t[j]也是单调排列的。这种双单调结构天然适合排序后线性扫描。正确做法是把司机数组S升序排序乘客等待上限数组T升序排序然后用双指针i遍历司机、j遍历乘客如果S[i] T[j]说明当前司机能服务当前乘客。这时匹配它们i和j都后移答案加1。如果S[i] T[j]说明当前接驾最快的司机也赶不上这位乘客的等待上限。那这位乘客无论如何都不可能被服务因为后面的司机更慢所以j后移放弃这个乘客。为什么贪心是最优的因为这个匹配问题的约束是司机要快、乘客要能等。把接驾时间最短的司机优先派给等待上限最小的乘客如果这样都匹配不上说明这个司机不可能匹配给任何乘客只能跳过如果匹配得上那这样匹配一定不会让最优解变差——因为等待上限越小的乘客对其他司机来说越挑剔把接驾最快的司机给它用就是资源用在最稀缺的地方。3.3 Python实现与多组用例验证代码非常简单核心就是排序加双指针def max_matches(drivers: list[int], orders: list[int]) - int: drivers.sort() orders.sort() i j ans 0 n, m len(drivers), len(orders) while i n and j m: if drivers[i] orders[j]: ans 1 i 1 j 1 else: j 1 return ans我写了一个简单测试来验证司机接驾耗时[5, 1, 3]乘客等待上限[2, 6, 4]排序后司机为[1, 3, 5]乘客为[2, 4, 6]。按代码走一遍司机1 乘客2匹配得1分司机3 乘客4匹配得2分司机5 乘客6匹配得3分。最终答案是3也就是所有人都匹配上了。如果换成司机[10, 20, 30]乘客[5, 15, 25]排序后司机10 乘客5跳过乘客5司机10 乘客15匹配司机20 乘客25匹配司机30没乘客了。答案是2正确。这种测试用例就是笔试时用来验证代码的最小样例。很多同学代码写完了不先跑自测样例就直接交结果连公开样例都没过很可惜。我在写题时习惯先构造三个用例功能用例验证算法逻辑边界用例验证空输入和单元素极端数据用例验证时间复杂度和溢出。3.4 从这道题看真题的包装风格我把这道题定义为模拟题是有原因的。和真正的2017年滴滴真题相比核心考点完全一样但真题的题目描述会比这个复杂得多会铺垫一个某城市高峰期同时出现大量订单的故事甚至会给一张表来说明司机和乘客的编号规则。看穿包装、提取模型的能力就是笔试最核心的能力。把这道题做透之后你会发现它还能迁移到很多变体里把接驾耗时换成外卖骑手到店时间把乘客等待上限换成外卖配送截止时间题目就变成了一道外卖平台的派单题再换一下把双方都换成任务处理时间和截止时间它又变成了一道通用的调度题。这就是母题的威力——你把一个模型的贪心正确性吃透了等于同时会做了十几道衍生题。4. 限时作答的实战策略读题顺序、暴力保底与边界陷阱4.1 先看数据范围再定算法方向平时刷题你可以在一个算法上磨一两个小时但笔试不行。90分钟做3-4道题平均一道只有20多分钟。所以拿到题目后的第一件事不是逐字读题而是先看输入规模。这是一个职业选手和业余玩家之间最明显的区别。我的判断逻辑是这样的n ≤ 20大概率是状态压缩DP、搜索或暴力枚举n ≤ 1000O(n^2)的DP或Floyd可以上n ≤ 10^5必须O(n log n)或O(n)排序、双指针、堆、二分常驻备选n ≤ 10^9不能遍历数据本身要找数学规律或二分答案。这个习惯救过我很多次。2017年滴滴就有道题题目给的是订单数量最多10^5很多人一上来就想用O(n^2)的DP写到一半发现跑不动才回头时间已经没了。实际上一看到10^5就该立刻往排序贪心或二分校验的方向想这种规模本身就是出题人给你的提示。4.2 暴力解拿部分分是笔试的保底策略在线笔试大部分都设置部分用例分也就是说你即使没想出最优解只要写一个能跑通小数据的暴力解法也能捞回15%到30%的分。这个原则在今天的校招笔试里依然适用而且非常重要别死磕一道题到最后一刻把确定能拿的分先拿到手。我见过太多人一道题想了40分钟没结果最后暴力也没来得及写整道题0分。正确的节奏是每道题先用5分钟想最优解想不出来就立刻写暴力解。暴力解写起来很快大概率能过30%左右的用例然后再回头继续想优化。这样至少保证每道题都有分对整体通过率的帮助非常可观。以第3章那道模拟题为例如果一下没想到排序双指针可以先写一个O(n*m)的双重循环暴力匹配——遍历每个司机找一个还没有被匹配且能接受他的乘客。这个暴力解法在n、m都小于100的情况下是完全能跑的能拿一部分分。4.3 边界条件与输入输出最容易丢分的隐形陷阱有编程题经验的都知道算法对了不代表能过。边界条件和输入输出处理是两大隐形失分点尤其在数据规模大到10^5的题目里这两个问题会被无限放大。边界条件方面要优先测试这些情况数组长度为0、s数组或t数组只有一个元素、所有司机都接不了任何订单、所有订单都能被任意司机接住、数值等于1或10^9、存在大量重复元素。这些用例不一定在公开样例里但一定在隐藏用例里。跑代码前先在脑子里过一遍心里有底。输入输出方面在线评测对格式要求严格多打一个空格、少换一次行都可能判错。输入可能是多行也可能一行内用逗号分隔读入时先确认清楚。Python的input()在大数据量时要改用sys.stdin.buffer.read()否则可能超时。这个小细节在n10^5时就可能决定你的代码能不能在限时内跑完。5. 校招编程题的备考方法论题型映射、复盘习惯与代码细节5.1 把真题归类成母题刷题才有效很多人刷了几百道题遇到新题还是没思路原因是刷题停留在这一道题的层面没有抽象成这一类题。我建议准备一个题型映射表把做过的题按考点归类。比如最短路类、最长递增子序列类、区间DP类、贪心排序类、并查集类、二分答案类。每归入一类题就写一行这类题的识别特征比如出现最大匹配、最小等待时间就优先想排序双指针。这个映射表是和2017年滴滴真题最好的相处方式因为它考的不是某道题本身而是你是否建立了这类映射。把那年的题吃透再用同样方法去拆解其他大厂的真题你会发现大多数题都能落进你已经建好的框架里。比如字节、美团、快手的笔试题目虽然叙事背景换了但核心考点的覆盖面和你从滴滴真题里整理出来的母题列表高度重合。5.2 笔试后复盘卡住的题才是最值钱的题笔试结束不等于这件事结束了。我自己的习惯是不管最后有没有过笔试后24小时内一定要把没做出来的题重新做一遍。因为这是你少有的带着现场压力思考过一轮的题大脑里已经留下了大量上下文这时候复盘效率最高。拖到第二天现场的思路和卡点就全忘了复盘效果大打折扣。复盘时重点回答三个问题我为什么没想到这个算法题目里哪个信息是解法的关键提示如果重新笔试我应该在哪个时间点放弃并转用暴力解把这三个问题的答案写下来这本错题本就是下一场笔试前最有价值的复习材料。它比任何刷题App里的收藏夹都好用因为那是你自己在压力状态下暴露出的真实思维漏洞。5.3 代码规范与手速笔试中的隐形得分项在笔试里很多人写字飞快变量名全是a、b、c函数逻辑堆在一个main里最后不但自己调试困难还容易因为小笔误丢分。实际上在线编程题对代码规范是有隐形要求的思路清晰、注释到位、函数拆分合理的代码即使某个用例没过批改人也更容易确认你的思路是对的酌情给分。相反一个逻辑全挤在一起、变量命名混乱的代码即使跑通了公开用例也容易在细节上暴露出问题。手速方面建议平时训练时就用一套固定的输入输出模板和代码风格形成肌肉记忆。比如我常年在笔试开头直接写import sys def main(): data sys.stdin.buffer.read().split() # 解析数据、调用算法逻辑 if __name__ __main__: main()把读入和主流程先写好再写具体逻辑。这样可以节省大量切换思路的时间也避免在紧张状态下犯低级语法错误。我后来想了想为什么这么多年过去每次看到校招笔试的编程题还会想起2017年滴滴这套题。不是因为它有多难而是它让我第一次意识到笔试考的从来不只是算法本身而是一个人在陌生问题面前保持冷静、快速建模、用代码落地验证的能力。这种能力在之后的每一次面试和项目中都用得上。如果这篇拆解能让你在下一场笔试里少一点手忙脚乱那就值了。