1. 滴滴出行2017秋招笔试这套编程题到底在考什么2017年滴滴出行秋季校招笔试算法题的风格相当典型表面上看都是经典题翻开卷子却发现每道题都裹着一层“共享出行”的外衣。我对这类考题特别有印象因为当年面试培训班里几乎人手一份考生回忆版真题汇总后来我还专门把这批题重新做了一遍发现它们的考察重心非常集中就是动态规划、图论、贪心和字符串处理这四块。很多刷完题的人最后都有一个共同感受题目并不是考你多偏多怪的算法而是在考你遇到业务描述时能不能第一时间把它翻译成熟悉的算法模型。先说这套题适合谁。如果你是准备投递互联网大厂后端、算法、测试开发岗位的应届生这批题值得刷如果你在工作几年后想补一补算法基础也可以用里面几道经典模型练手。题目本身的难度是中等偏上没有特别变态的题目但非常考验“读题能力和模型抽象能力”换言之光会背模板没用得先把业务描述翻译成算法问题。你现在看这套 2017 年的题可能会觉得有些场景熟悉比如“司机连续接单”“城市间最短路线”这些本质上都是把常见算法模板套上出行行业的皮放在今天依然是校招笔试里非常主流的一种出题方式。1.1 真题整体结构回忆根据当年考生在各类社区里整理出来的信息滴滴 2017 秋招笔试的编程题通常是 3 到 4 道大题总时长在 90 分钟左右。我在下面列出的就是被讨论最多、重复出现在不同场次里的四道题它们并不是同一套试卷的完整原题而是把多个版本的回忆版拼起来做的归纳这一点先说明清楚免得你对着序号去纠结“这到底是不是当年第一题”。我整理出的四道核心题分别是环状数组的最大子段和、字符串编辑距离、城市间最短路线规划、订单时段调度。其中最大子段和是典型动态规划编辑距离是二维动态规划最短路是图论经典题订单调度是贪心题。这个组合几乎覆盖了后端校招笔试的“必考清单”所以你在准备其他家的时候也可以用同样框架去对题。编号题目场景算法模型难度核心考点1环形路线连续接单环形数组最大子段和中等动态规划、边界情况2字符串改写编辑距离中等二维DP、滚动数组3城市间最短时间单源最短路中等偏上Dijkstra、堆优化4订单时段调度区间调度 / 加权调度中等贪心、二分DP单独看每一道都没有超出常见算法模板的范围难就难在你要在 90 分钟内连续完成四道并且每道题都要读题、建模、写代码、跑边界。所以准备这套题本质上是在训练“快速建模能力”而不是单纯背题。很多同学刷题量不小但一到笔试就崩不是因为算法没学会而是因为前面读题慢了十分钟后面又在一道题上钻牛角尖时间全不够用。1.2 为什么滴滴偏爱“业务包装题”很多考生当年吐槽说这套题有意把算法题包装成业务场景。举个例子如果直接给一个“环状数组最大子段和”很多人闭着眼睛就能写 Kadane 算法一旦题目写成“司机在环形路线上连续接单收益最大”就容易在建模阶段卡住。对面试官来说这种包装是有意为之的他们想筛选的不是会背模板的人而是能快速把业务问题抽象成数学/算法模型的人。这也是为什么我建议你在刷题时不要跳过“读题”这个环节。我见过太多同学做这道题时一看到“最大子段和”就直接写循环数组解法结果忽略了题目里可能还有一个附加条件比如“连续子段长度不能超过 n”或者“至少选一个点”。这些细节才是笔试拉开差距的地方。模型的名称不重要题目里那些限定词才重要。你平时刷题可能习惯看题目标签知道这是 DP、那是贪心但真实笔试不会给你打好标签不会告诉你这题用哪种算法一切都要自己从题干里挖。2. 四道题的难度梯度与准备策略2.1 先看输入规模再决定算法校招笔试题目很少会把数据范围写得特别直白但你能从输入描述里推断。比如城市数 n 如果只有 100你用 Floyd 最短路也能过如果 n 到 10^5那就必须写堆优化的 Dijkstra。很多同学算法课学得不错但一到笔试就不会看数据范围结果写了个 O(n^2) 的代码直接超时。我在下面做一个简单的“规模→算法倾向”对照刷题时可以拿来当参考。数据范围建议算法倾向理由n ≤ 20状态压缩、暴力搜索指数级可以接受n ≤ 1000O(n^2) DP二维表能开下n ≤ 10^5O(n log n) 排序/二分/堆不能再平方n ≤ 10^6O(n) 或 O(n log n)注意常数和内存这个表不是万能公式但能帮你在正式做题前形成一个初步判断。我看到很多人在笔试里只盯着“算法名”去想却忘了先看数据范围。比如区间调度题 n10^5那贪心排序 O(n log n) 是稳的如果 n2000你就算用 O(n^2) 的 DP 也能跑不需要强行优化。数据范围决定了你能接受的复杂度上限也决定了你该用什么思路破题。2.2 四个必须提前准备好的模板如果只给你 48 小时准备这套题我建议优先把下面四个模板练到肌肉记忆Kadane 算法、二维 DP 滚动数组、Dijkstra优先队列、区间排序贪心。这四个模板可以覆盖滴滴这套题里大约 80% 的分数。多出来的 20% 是边界讨论比如负数、空数组、重复区间、图不连通这些要靠刷题经验来补。我的经验是每个模板都准备两种写法一种是“最简洁但容易炸边界”的写法另一种是“带边界保护但稍长”的写法。笔试时用第二种面试手撕代码时用第一种顺便讲思路这样两头都不吃亏。比如 Dijkstra 里那句 if d dist[u]: continue很多精简模板没有但笔试里如果没有这一句就可能在稠密图上反复入堆导致超时。像这种细节最好提前写进模板里而不是现场临时想。2.3 读题建模的三步法拿到一道笔试编程题我习惯按三步走。第一步把题干里的名词划掉换成算法名词比如“站点”换成“数组元素”“订单时间”换成“区间”“道路行驶时间”换成“边权”第二步圈出形容词和动词比如“连续”“最大”“最少”“重叠”这些词直接决定选 DP 还是贪心第三步把数据范围抄到草稿纸上作为算法选型的硬约束。这套方法听起来很简单但真正做到位的人不多。我观察过一些同学的刷题过程他们往往在读完题后 30 秒内就开始写代码结果写到一半才发现少考虑了一个条件。笔试环境中这种返工非常致命因为时间本来就不够用。你宁可多花五分钟把模型想清楚也不要对着一个“快写出来的错误解法”改来改去。3. 环形数组最大子段和经典 DP 的边界大考验3.1 题目原型与数学转化题目大概长这样某条环形路线上有 n 个站点每个站点有一个收益值可能为负司机可以任选一个方向绕圈也可以在半途下车要求选取一段连续的站点停靠使得收益总和最大。说白了它就是一个环状数组让你求最大连续子段和。这里有个容易被忽略的数学点环状数组的最大子段和要么出现在常规的“非环”范围内要么跨越起点和终点也就是包含整个数组的“总和减去最小子段和”。为什么跨越起点和终点的情况可以用“总和减去最小子段和”来表示因为在一个环上如果我们要选一段跨过首尾那么这段之外的部分正好就是数组中间某段“不需要选”的连续区域。为了让选择的收益最大我们自然希望不选的部分收益尽可能小于是问题就变成了找“最小子段和”。这个转化是整个题目的题眼理解了它代码反而只是顺手的事。很多同学上来就套循环数组转换成两倍数组的解法但如果你没理解上面这个等价关系题目一变条件就容易懵。3.2 Kadane 状态与初始化细节先复习一下经典 Kadane 算法。用 dp[i] 表示“以第 i 个元素结尾的最大子段和”转移公式一句话要么把当前元素接到前面的最优段后面要么从当前元素重新开始。dp[i] max(dp[i-1] a[i], a[i])如果要求最小子段和把 max 换成 min 就行或者把所有数字取负再跑一遍 Kadane。这里要特别说明如果整个数组全部是负数那“最大子段和”等于数组中最大的那个负数直接返回 max(a)而如果套用了“sum - min_subarray”的公式当所有数都是负数时minSubArray 会等于整个数组的和导致 sum - minSubArray 0这明显不符合“至少选一个站点”的题意。所以代码里要加一个特判。3.3 完整代码实现def max_subarray_sum(nums): # 标准 Kadane求非环情况下的最大子段和 cur_max 0 global_max float(-inf) for x in nums: cur_max