每年校招季结束我都会把当年做过的笔试翻出来重新做一遍。最近在整理旧电脑里的代码存档翻到2019年投递小马智行pony.ai时做的那套校招真题看着当时的答题代码和草稿纸忍不住按现在的思路重做了一遍。这个系列先从第一套开始写里面有三道题合并测试时段、模块依赖排序、车队调度。题目本身都是算法题里非常经典的题型但包装在自动驾驶的业务场景里之后读题和建模反而成了最大的门槛。如果你是准备自动驾驶公司校招或者想看看算法题怎么和工程问题结合的这篇复盘应该对你有用。1. 这套题的整体观感看似工程题其实全是基本功1.1 为什么我直到今天还在复盘这套题2019年那会儿自动驾驶赛道正热小马智行这类公司的校招笔试基本是标配算法题。我投的是算法岗收到笔试链接后找了个安静的晚上掐着时间做完了整套题。当时最大的感受是题目难度不算夸张但每一道都裹着一层“自动驾驶业务”的外壳读题的时间比写代码的时间还长。现在回头看这套题恰好代表了自动驾驶公司算法笔试的一个典型风格不考偏题怪题而是把经典的区间合并、拓扑排序、堆贪心包装成测试路段、模块依赖、车队调度这样的业务场景考察你能不能把一个含糊的工程问题翻译成清晰的算法模型。这个能力在自动驾驶行业比在普通互联网公司更重要因为真实的路测数据、传感器数据、调度系统里到处都是这种需要先建模再解决的问题。1.2 自动驾驶公司笔试和互联网大厂笔试的差异当时我也做过不少互联网大厂的笔试题对比下来差距非常明显。普通大厂的算法题会给一个很干净的数学描述比如“给定一个数组返回两个数和为target的下标”输入输出定义得明明白白但自动驾驶公司的题会让你自己从一段业务描述里提取出数据结构。对比维度互联网大厂典型笔试题自动驾驶公司典型笔试题题面风格数学化、抽象化直接给数组/图业务化、场景化需要自己建模输入输出格式固定边界条件明确描述相对口语化边界定义要自己判断核心考点算法熟练度算法熟练度 场景理解力典型例子合并区间 [[1,3],[2,6]]“统计测试车队的覆盖总时长”这不是说哪种更好而是公司业务形态决定的。自动驾驶公司需要的人不只是会写排序和搜索还要能从一堆路测日志、任务描述里找到问题的本质。这套真题其实就是在用笔试的形式提前模拟了这份工作的一部分日常。2. 第一题测试时段合并考的其实是区间覆盖2.1 题目复盘测试车辆上报的行驶记录题目描述大概是这样的一个自动驾驶测试车队在某测试路段上运行每辆车会按照时间上报一条行驶记录。现在有n条记录每条记录包含两个整数start和end表示该车在某段测试路段上的行驶开始时间和结束时间。需要你统计整个车队实际覆盖的总时长——也就是说重叠的行驶时间段要合并只算一次。为了让大家有直观感觉我把当时的输入输出样例整理在这里时间取整按左闭右开区间理解即end - start就是时长输入 4 1 3 2 6 8 10 15 18 输出 10解释一下样例[1,3]和[2,6]在时间轴上有重叠合并成[1,6]时长为5[8,10]时长为2[15,18]时长为3。合并后的总时长是5 2 3 10。如果不合并直接相加会得到3 4 2 3 12多算了重叠部分。2.2 如何从业务描述变换到区间合并模型这一步是关键也是很多人第一眼没反应过来的地方。“统计车队实际覆盖总时长”这句话翻译过来就是给定若干个区间合并所有重叠区间然后计算这些不相交区间的长度之和。标准解法就是排序加贪心。我当时的分析过程是分三步走的先把每条记录抽象成一个区间[start, end]确认题目关注的是“覆盖总时长”而不是具体哪辆车覆盖哪个时间段。判断“相接”是否算重叠。这题里面如果一辆车结束时间是3另一辆车开始时间是3这段覆盖是连续的应该合并。这个细节决定了代码里是if start cur_end还是if start cur_end。想清楚边界条件记录可能乱序可能完全包含也可能只有一条记录。做完这三步问题就从一个“车队业务”变成了标准的区间合并直接用模板就能过。2.3 排序加贪心的代码实现与复杂度分析确定思路后代码本身其实很短。核心逻辑是按开始时间排序然后逐个扫描区间。如果当前区间的开始时间小于等于已合并区间的结束时间说明有重叠把结束时间更新为两者中较大的值否则说明遇到了一个不相交的新区间先把前一个合并好的区间结算掉再开始新的合并。def merge_coverage(records): if not records: return 0 records.sort(keylambda x: x[0]) total 0 cur_start, cur_end records[0] for start, end in records[1:]: if start cur_end: # 有重叠合并区间注意取较大的结束时间 cur_end max(cur_end, end) else: # 没有重叠结算当前区间 total cur_end - cur_start cur_start, cur_end start, end # 结算最后一个区间 total cur_end - cur_start return total时间复杂度是O(n log n)排序占主导空间复杂度O(1)不考虑输入存储。对于n 10^5的常见数据范围这个解法完全够用。为什么贪心是对的因为按起点排序之后一旦遇到一个起点大于当前合并区间终点的新区间后面所有区间的起点只会更大因此当前合并区间不可能再和后面的任何区间发生重叠此时结算是安全的。2.4 现场容易翻车的边界点这道题我在笔试现场没有一次写对原因是漏了一个非常隐蔽的边界。这里把踩过的坑都列出来空输入n0时records为空直接返回0。不处理的话会在records[0]这里报IndexError。记录完全包含比如[1,10]和[2,3]扫描到[2,3]时start2 cur_end10需要更新cur_end max(10, 3) 10不能直接cur_end end否则会把覆盖区间缩短。相接区间start cur_end时到底算不算重叠在“覆盖总时长”的语义下相接意味着时间连续应该算作同一段覆盖合并后总时长才是对的。这一点必须根据题目描述确认。输入乱序排序不能省我第一次写的时候想着“记录是按时间顺序给的吧”结果样例都过不了因为题目压根没保证这一点。3. 第二题模块依赖启动顺序拓扑排序的工程化考法3.1 题面还原一份启动顺序表第二题在场景上直接切到了自动驾驶系统的软件架构。题目大致是说自动驾驶系统包含n个功能模块编号从0到n-1例如传感器驱动、感知、定位、规划、控制等等。某些模块必须在另一些模块之后启动比如规划模块必须等感知模块和定位模块运行起来后才能开始工作。现在给了m组依赖关系每组是一个二元组[a, b]表示模块a依赖模块b也就是b必须先于a启动。要求输出一个合法的模块启动顺序如果模块依赖关系存在循环依赖则系统无法正常启动需要输出错误提示。当时的样例我整理成下面这样输入 5 4 1 0 2 0 3 1 4 1 输出 0 1 3 2 4这里n5m4。模块1和2都依赖0模块3和4都依赖1。输出0 1 3 2 4是一个合法顺序因为它保证了每个模块启动时它依赖的模块已经启动过了。3.2 为什么选Kahn算法而不是DFS拓扑排序有两种主流实现Kahn算法基于BFS的入度削减法和DFS深度优先遍历利用递归栈顺序输出。我当时选择了Kahn算法原因有三个环检测更直观Kahn算法在处理完所有入度为0的节点后如果删除的节点数量小于总节点数说明图中存在环。这个判断是一行代码的事情。避免递归爆栈真题数据范围写着n, m在10^5级别。如果用递归DFSPython默认递归深度约1000很容易栈溢出还得手动设置sys.setrecursionlimit多一层风险。和工程直觉更匹配实际做模块启动顺序规划时从“没有依赖的模块先启动”这个角度思考非常自然。当然DFS也能做而且对于某些需要输出“字典序最小”的变种DFS的思路也有用武之地。但作为笔试第一时间的解法Kahn算法是我最推荐的。3.3 完整实现队列维护入度为0的节点Kahn算法的核心是维护每个节点的入度。初始时所有入度为0的节点都可以直接启动放入队列。每取出一个节点并“启动”就把以它为前置依赖的所有节点的入度减1如果某个节点的入度因此变成0说明它的前置条件都满足了可以加入队列。from collections import deque def topo_sort(n, edges): indeg [0] * n graph [[] for _ in range(n)] for to, pre in edges: graph[pre].append(to) indeg[to] 1 q deque([i for i in range(n) if indeg[i] 0]) order [] while q: u q.popleft() order.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) if len(order) ! n: return cycle detected return order注意建图方向edges给的是[a, b]表示a依赖b所以从b有一条有向边指向a。建图时写成graph[pre].append(to)即从被依赖的模块指向依赖它的模块后续删除依赖时也从这里走。这个解法的时间复杂度是O(n m)空间复杂度是O(n m)属于图题里的标准最优解。3.4 面试官还会追问什么笔试做完了不代表这个知识点就结束了。后来我在准备面试时发现围绕这道题面试官非常喜欢做三个方向的延伸循环依赖的定位如果存在环不止要报“cycle detected”最好还能输出环上的模块节点。做法是在Kahn算法结束后所有入度还不为0也就是没被删除的节点都可能在环上用DFS可以进一步把具体的环找出来。输出字典序最小的拓扑序列如果题目要求多个合法顺序里输出字典序最小把普通队列换成优先队列最小堆每次取编号最小的入度为0节点即可。动态依赖如果模块依赖关系在运行中会变化无法一次性拿到全量图这就属于在线拓扑排序的范畴工程上通常用事件驱动的方式维护入度变化。这三个方向前两个在面试手撕代码环节很常见第三个更多是结合实际系统设计来聊。能把第三点聊清楚说明你对拓扑排序的理解已经超越“背模板”的层次了。4. 第三题最少测试车辆数堆贪心和扫描线的取舍4.1 题面还原同一辆车不能同时跑两个任务第三题的场景挂在了车队调度上测试部门有一批道路测试任务每个任务占用一辆测试车任务有明确的开始时间和结束时间一辆车同一时刻只能执行一个任务。现在给了n个任务各自的起止时间问最少需要配置多少辆测试车才能保证所有任务都能按时执行。这本质上就是经典的会议室问题Meeting Rooms II。当时看到这题时我甚至有点怀疑自己看错了因为它几乎是LeetCode原题。但别高兴得太早题目的数据规模到了10^5而且时间值跨度很大不能用简单的数组标记法。样例是这样的输入 3 0 30 5 10 15 20 输出 2三个任务中0-30的任务全程占着一辆车5-10和15-20因为都和0-30重叠没法复用这辆车所以至少需要2辆车。复用的机会在于一个任务结束后同一辆车可以接下一个任务只要下一个任务的开始时间不早于当前任务的结束时间。4.2 核心逻辑最小堆维护最早可用时间贪心策略非常直接按开始时间从小到大处理所有任务用一个最小堆维护“当前正在被占用的车辆”的结束时间每来一个新任务先看堆顶——也就是最早空闲的那辆车——它的结束时间是否小于等于当前任务开始时间。如果是这辆车可以复用先弹出去然后把当前任务的结束时间压入堆。最终堆的大小就是同时进行的最大任务数也就是最少需要的车辆数。import heapq def min_vehicles(tasks): tasks.sort(keylambda x: x[0]) heap [] for start, end in tasks: if heap and heap[0] start: heapq.heappop(heap) heapq.heappush(heap, end) return len(heap)为什么堆顶就是最早结束的车因为最小堆保证堆顶元素是堆里最小的结束时间。如果这辆车都不能在当前任务开始时空闲那其他车更不可能所以当前任务必须另开新车。复杂度排序O(n log n)每个任务最多出入堆一次堆操作O(log n)总体O(n log n)空间O(n)。4.3 如果题目升级为输出具体车辆安排笔试一般只要求输出车辆数但面试官经常会加一句“能不能把每辆车的任务序列打印出来”。这时候堆里就不能只存结束时间了得存一个(end_time, vehicle_id)的元组同时维护一个车辆列表。每来一个任务如果堆顶可复用取出的vehicle_id就给当前任务用否则创建一辆新车id递增。import heapq def assign_vehicles(tasks): tasks [(s, e, i) for i, (s, e) in enumerate(tasks)] tasks.sort(keylambda x: x[0]) heap [] # (end_time, vehicle_id) vehicle_tasks [] for start, end, task_id in tasks: if heap and heap[0][0] start: end_time, vid heapq.heappop(heap) else: vid len(vehicle_tasks) vehicle_tasks.append([]) heapq.heappush(heap, (end, vid)) vehicle_tasks[vid].append(task_id) return len(vehicle_tasks), vehicle_tasks这个版本已经接近真实调度系统的雏形了。实际业务里还会加更多约束比如车辆有不同的传感器配置某些任务只能由特定车型执行那就是更复杂的资源匹配问题了但核心的不相交区间复用思想是一样的。4.4 另一种思路扫描线求最大重叠数除了堆贪心还有一个角度可以解这题最少车辆数等于同一时刻最多有多少个任务在重叠也就是区间重叠的最大深度。用差分数组或扫描线来做把所有开始时间标记为1所有结束时间标记为-1然后按时间顺序扫一遍维护当前同时运行的任务数取最大值。def min_vehicles_by_sweep(tasks): events [] for start, end in tasks: events.append((start, 1)) events.append((end, -1)) events.sort(keylambda x: (x[0], x[1])) cur 0 max_cur 0 for _, delta in events: cur delta max_cur max(max_cur, cur) return max_cur注意排序时同一时间点上要先处理结束事件-1再处理开始事件1保证“一个任务刚结束另一个任务马上开始”的情况下可以复用车辆。写成(x[0], x[1])排序就是让-1排在1前面。两种做法性能差不多但堆贪心更符合“调度”的直觉扫描线更符合“数学建模”的直觉。笔试时写出任何一种都能拿满分我建议选自己最熟悉的那种而不是在现场临时切换思路。5. 复盘这套题真正在选拔什么能力5.1 审题与建模是笔试的分水岭把这三道题放在一起看会发现一个共同点没有一道题把算法名字写在题目里。区间合并被写成了“统计覆盖总时长”拓扑排序被写成了“输出模块启动顺序”堆贪心被写成了“最少需要多少辆测试车”。很多人考完抱怨说“题目读不懂”本质上不是语文问题而是缺少把业务描述抽象成数据结构的训练。我自己的经验是拿到一道场景化算法题先不要急着写代码用两分钟在草稿纸上画出三样东西输入是什么输出是什么中间要维护什么样的数据结构。比如第一题输入是区间列表输出是总长度中间要维护的是“当前合并区间”第二题输入是图输出是线性序列中间要维护的是“入度为0的节点集合”。模型一旦确定后面就是默写模板。5.2 代码规范和自测习惯比想象中重要笔试的判题系统不会因为你的代码风格好看给分但自测习惯绝对会影响分数。三道题里第一题如果不处理空输入样例可能直接崩第二题如果建的图方向反了样例输出完全对不上第三题如果排序时没处理同时间点的结束和开始顺序边界数据就会错。我后来带人准备笔试时反复强调一个自查清单输入为空时我的代码是否还能跑最极端情况所有区间重叠 / 完全不重叠 / 完全包含是否输出符合预期题目里的“相接算不算重叠”“结束时间和开始时间相同时能不能复用”这类细节确认了吗数据规模是10^5还是10^9如果是后者O(n^2)的解法直接淘汰。这套题的三道题数据规模都指向O(n log n)解法真有人上来用O(n^2)的暴力扫描做第一题在小数据上可能看不出来问题但大数据一定超时。5.3 给准备自动驾驶公司校招的同学三个建议如果你现在正在准备自动驾驶公司算法岗的校招以这套题和后续我参加面试的经验给你三个实操性很强的建议把LeetCode中等题刷到“闭着眼睛能默写”的程度。区间合并、拓扑排序、会议室这类题属于高频考点每年换个业务包装反复出现。不要只满足于AC要能把边界条件原原本本说出来。练习场景题建模。看到任何题目不管它讲的是车还是外卖还是直播先尝试用“输入-数据结构-输出”框架拆解。这个能力不只在笔试有用在后面的技术面、HR面聊项目时都会成为加分项。多写Python代码但要注意性能细节。自动驾驶公司笔试不少支持Python但Python的递归深度、大常数都很吃亏。能用迭代就不用递归能用数组模拟的优先队列就别手写堆这些细节会在关键时刻帮你省下调试时间。最后分享一个我自己踩过的坑。当年做第一题时我把相接区间算成了不重叠导致输出和预期结果差了一小节检查了很久才发现是自己对题目里“覆盖”的理解有偏差。后来我养成了一个习惯任何一道区间类题目动笔前先问自己三个问题——区间是开还是闭相接算不算重叠输出要的是合并后的区间还是只需要长度这三个问题弄明白了区间题基本不会出错。这套真题我后来又刷过几遍每次重新做都会有新的体会面试和实际工作中处理时间窗口、任务调度这些问题时当年的基础帮了大忙。
自动驾驶校招真题复盘：区间合并、拓扑排序与堆贪心
每年校招季结束我都会把当年做过的笔试翻出来重新做一遍。最近在整理旧电脑里的代码存档翻到2019年投递小马智行pony.ai时做的那套校招真题看着当时的答题代码和草稿纸忍不住按现在的思路重做了一遍。这个系列先从第一套开始写里面有三道题合并测试时段、模块依赖排序、车队调度。题目本身都是算法题里非常经典的题型但包装在自动驾驶的业务场景里之后读题和建模反而成了最大的门槛。如果你是准备自动驾驶公司校招或者想看看算法题怎么和工程问题结合的这篇复盘应该对你有用。1. 这套题的整体观感看似工程题其实全是基本功1.1 为什么我直到今天还在复盘这套题2019年那会儿自动驾驶赛道正热小马智行这类公司的校招笔试基本是标配算法题。我投的是算法岗收到笔试链接后找了个安静的晚上掐着时间做完了整套题。当时最大的感受是题目难度不算夸张但每一道都裹着一层“自动驾驶业务”的外壳读题的时间比写代码的时间还长。现在回头看这套题恰好代表了自动驾驶公司算法笔试的一个典型风格不考偏题怪题而是把经典的区间合并、拓扑排序、堆贪心包装成测试路段、模块依赖、车队调度这样的业务场景考察你能不能把一个含糊的工程问题翻译成清晰的算法模型。这个能力在自动驾驶行业比在普通互联网公司更重要因为真实的路测数据、传感器数据、调度系统里到处都是这种需要先建模再解决的问题。1.2 自动驾驶公司笔试和互联网大厂笔试的差异当时我也做过不少互联网大厂的笔试题对比下来差距非常明显。普通大厂的算法题会给一个很干净的数学描述比如“给定一个数组返回两个数和为target的下标”输入输出定义得明明白白但自动驾驶公司的题会让你自己从一段业务描述里提取出数据结构。对比维度互联网大厂典型笔试题自动驾驶公司典型笔试题题面风格数学化、抽象化直接给数组/图业务化、场景化需要自己建模输入输出格式固定边界条件明确描述相对口语化边界定义要自己判断核心考点算法熟练度算法熟练度 场景理解力典型例子合并区间 [[1,3],[2,6]]“统计测试车队的覆盖总时长”这不是说哪种更好而是公司业务形态决定的。自动驾驶公司需要的人不只是会写排序和搜索还要能从一堆路测日志、任务描述里找到问题的本质。这套真题其实就是在用笔试的形式提前模拟了这份工作的一部分日常。2. 第一题测试时段合并考的其实是区间覆盖2.1 题目复盘测试车辆上报的行驶记录题目描述大概是这样的一个自动驾驶测试车队在某测试路段上运行每辆车会按照时间上报一条行驶记录。现在有n条记录每条记录包含两个整数start和end表示该车在某段测试路段上的行驶开始时间和结束时间。需要你统计整个车队实际覆盖的总时长——也就是说重叠的行驶时间段要合并只算一次。为了让大家有直观感觉我把当时的输入输出样例整理在这里时间取整按左闭右开区间理解即end - start就是时长输入 4 1 3 2 6 8 10 15 18 输出 10解释一下样例[1,3]和[2,6]在时间轴上有重叠合并成[1,6]时长为5[8,10]时长为2[15,18]时长为3。合并后的总时长是5 2 3 10。如果不合并直接相加会得到3 4 2 3 12多算了重叠部分。2.2 如何从业务描述变换到区间合并模型这一步是关键也是很多人第一眼没反应过来的地方。“统计车队实际覆盖总时长”这句话翻译过来就是给定若干个区间合并所有重叠区间然后计算这些不相交区间的长度之和。标准解法就是排序加贪心。我当时的分析过程是分三步走的先把每条记录抽象成一个区间[start, end]确认题目关注的是“覆盖总时长”而不是具体哪辆车覆盖哪个时间段。判断“相接”是否算重叠。这题里面如果一辆车结束时间是3另一辆车开始时间是3这段覆盖是连续的应该合并。这个细节决定了代码里是if start cur_end还是if start cur_end。想清楚边界条件记录可能乱序可能完全包含也可能只有一条记录。做完这三步问题就从一个“车队业务”变成了标准的区间合并直接用模板就能过。2.3 排序加贪心的代码实现与复杂度分析确定思路后代码本身其实很短。核心逻辑是按开始时间排序然后逐个扫描区间。如果当前区间的开始时间小于等于已合并区间的结束时间说明有重叠把结束时间更新为两者中较大的值否则说明遇到了一个不相交的新区间先把前一个合并好的区间结算掉再开始新的合并。def merge_coverage(records): if not records: return 0 records.sort(keylambda x: x[0]) total 0 cur_start, cur_end records[0] for start, end in records[1:]: if start cur_end: # 有重叠合并区间注意取较大的结束时间 cur_end max(cur_end, end) else: # 没有重叠结算当前区间 total cur_end - cur_start cur_start, cur_end start, end # 结算最后一个区间 total cur_end - cur_start return total时间复杂度是O(n log n)排序占主导空间复杂度O(1)不考虑输入存储。对于n 10^5的常见数据范围这个解法完全够用。为什么贪心是对的因为按起点排序之后一旦遇到一个起点大于当前合并区间终点的新区间后面所有区间的起点只会更大因此当前合并区间不可能再和后面的任何区间发生重叠此时结算是安全的。2.4 现场容易翻车的边界点这道题我在笔试现场没有一次写对原因是漏了一个非常隐蔽的边界。这里把踩过的坑都列出来空输入n0时records为空直接返回0。不处理的话会在records[0]这里报IndexError。记录完全包含比如[1,10]和[2,3]扫描到[2,3]时start2 cur_end10需要更新cur_end max(10, 3) 10不能直接cur_end end否则会把覆盖区间缩短。相接区间start cur_end时到底算不算重叠在“覆盖总时长”的语义下相接意味着时间连续应该算作同一段覆盖合并后总时长才是对的。这一点必须根据题目描述确认。输入乱序排序不能省我第一次写的时候想着“记录是按时间顺序给的吧”结果样例都过不了因为题目压根没保证这一点。3. 第二题模块依赖启动顺序拓扑排序的工程化考法3.1 题面还原一份启动顺序表第二题在场景上直接切到了自动驾驶系统的软件架构。题目大致是说自动驾驶系统包含n个功能模块编号从0到n-1例如传感器驱动、感知、定位、规划、控制等等。某些模块必须在另一些模块之后启动比如规划模块必须等感知模块和定位模块运行起来后才能开始工作。现在给了m组依赖关系每组是一个二元组[a, b]表示模块a依赖模块b也就是b必须先于a启动。要求输出一个合法的模块启动顺序如果模块依赖关系存在循环依赖则系统无法正常启动需要输出错误提示。当时的样例我整理成下面这样输入 5 4 1 0 2 0 3 1 4 1 输出 0 1 3 2 4这里n5m4。模块1和2都依赖0模块3和4都依赖1。输出0 1 3 2 4是一个合法顺序因为它保证了每个模块启动时它依赖的模块已经启动过了。3.2 为什么选Kahn算法而不是DFS拓扑排序有两种主流实现Kahn算法基于BFS的入度削减法和DFS深度优先遍历利用递归栈顺序输出。我当时选择了Kahn算法原因有三个环检测更直观Kahn算法在处理完所有入度为0的节点后如果删除的节点数量小于总节点数说明图中存在环。这个判断是一行代码的事情。避免递归爆栈真题数据范围写着n, m在10^5级别。如果用递归DFSPython默认递归深度约1000很容易栈溢出还得手动设置sys.setrecursionlimit多一层风险。和工程直觉更匹配实际做模块启动顺序规划时从“没有依赖的模块先启动”这个角度思考非常自然。当然DFS也能做而且对于某些需要输出“字典序最小”的变种DFS的思路也有用武之地。但作为笔试第一时间的解法Kahn算法是我最推荐的。3.3 完整实现队列维护入度为0的节点Kahn算法的核心是维护每个节点的入度。初始时所有入度为0的节点都可以直接启动放入队列。每取出一个节点并“启动”就把以它为前置依赖的所有节点的入度减1如果某个节点的入度因此变成0说明它的前置条件都满足了可以加入队列。from collections import deque def topo_sort(n, edges): indeg [0] * n graph [[] for _ in range(n)] for to, pre in edges: graph[pre].append(to) indeg[to] 1 q deque([i for i in range(n) if indeg[i] 0]) order [] while q: u q.popleft() order.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) if len(order) ! n: return cycle detected return order注意建图方向edges给的是[a, b]表示a依赖b所以从b有一条有向边指向a。建图时写成graph[pre].append(to)即从被依赖的模块指向依赖它的模块后续删除依赖时也从这里走。这个解法的时间复杂度是O(n m)空间复杂度是O(n m)属于图题里的标准最优解。3.4 面试官还会追问什么笔试做完了不代表这个知识点就结束了。后来我在准备面试时发现围绕这道题面试官非常喜欢做三个方向的延伸循环依赖的定位如果存在环不止要报“cycle detected”最好还能输出环上的模块节点。做法是在Kahn算法结束后所有入度还不为0也就是没被删除的节点都可能在环上用DFS可以进一步把具体的环找出来。输出字典序最小的拓扑序列如果题目要求多个合法顺序里输出字典序最小把普通队列换成优先队列最小堆每次取编号最小的入度为0节点即可。动态依赖如果模块依赖关系在运行中会变化无法一次性拿到全量图这就属于在线拓扑排序的范畴工程上通常用事件驱动的方式维护入度变化。这三个方向前两个在面试手撕代码环节很常见第三个更多是结合实际系统设计来聊。能把第三点聊清楚说明你对拓扑排序的理解已经超越“背模板”的层次了。4. 第三题最少测试车辆数堆贪心和扫描线的取舍4.1 题面还原同一辆车不能同时跑两个任务第三题的场景挂在了车队调度上测试部门有一批道路测试任务每个任务占用一辆测试车任务有明确的开始时间和结束时间一辆车同一时刻只能执行一个任务。现在给了n个任务各自的起止时间问最少需要配置多少辆测试车才能保证所有任务都能按时执行。这本质上就是经典的会议室问题Meeting Rooms II。当时看到这题时我甚至有点怀疑自己看错了因为它几乎是LeetCode原题。但别高兴得太早题目的数据规模到了10^5而且时间值跨度很大不能用简单的数组标记法。样例是这样的输入 3 0 30 5 10 15 20 输出 2三个任务中0-30的任务全程占着一辆车5-10和15-20因为都和0-30重叠没法复用这辆车所以至少需要2辆车。复用的机会在于一个任务结束后同一辆车可以接下一个任务只要下一个任务的开始时间不早于当前任务的结束时间。4.2 核心逻辑最小堆维护最早可用时间贪心策略非常直接按开始时间从小到大处理所有任务用一个最小堆维护“当前正在被占用的车辆”的结束时间每来一个新任务先看堆顶——也就是最早空闲的那辆车——它的结束时间是否小于等于当前任务开始时间。如果是这辆车可以复用先弹出去然后把当前任务的结束时间压入堆。最终堆的大小就是同时进行的最大任务数也就是最少需要的车辆数。import heapq def min_vehicles(tasks): tasks.sort(keylambda x: x[0]) heap [] for start, end in tasks: if heap and heap[0] start: heapq.heappop(heap) heapq.heappush(heap, end) return len(heap)为什么堆顶就是最早结束的车因为最小堆保证堆顶元素是堆里最小的结束时间。如果这辆车都不能在当前任务开始时空闲那其他车更不可能所以当前任务必须另开新车。复杂度排序O(n log n)每个任务最多出入堆一次堆操作O(log n)总体O(n log n)空间O(n)。4.3 如果题目升级为输出具体车辆安排笔试一般只要求输出车辆数但面试官经常会加一句“能不能把每辆车的任务序列打印出来”。这时候堆里就不能只存结束时间了得存一个(end_time, vehicle_id)的元组同时维护一个车辆列表。每来一个任务如果堆顶可复用取出的vehicle_id就给当前任务用否则创建一辆新车id递增。import heapq def assign_vehicles(tasks): tasks [(s, e, i) for i, (s, e) in enumerate(tasks)] tasks.sort(keylambda x: x[0]) heap [] # (end_time, vehicle_id) vehicle_tasks [] for start, end, task_id in tasks: if heap and heap[0][0] start: end_time, vid heapq.heappop(heap) else: vid len(vehicle_tasks) vehicle_tasks.append([]) heapq.heappush(heap, (end, vid)) vehicle_tasks[vid].append(task_id) return len(vehicle_tasks), vehicle_tasks这个版本已经接近真实调度系统的雏形了。实际业务里还会加更多约束比如车辆有不同的传感器配置某些任务只能由特定车型执行那就是更复杂的资源匹配问题了但核心的不相交区间复用思想是一样的。4.4 另一种思路扫描线求最大重叠数除了堆贪心还有一个角度可以解这题最少车辆数等于同一时刻最多有多少个任务在重叠也就是区间重叠的最大深度。用差分数组或扫描线来做把所有开始时间标记为1所有结束时间标记为-1然后按时间顺序扫一遍维护当前同时运行的任务数取最大值。def min_vehicles_by_sweep(tasks): events [] for start, end in tasks: events.append((start, 1)) events.append((end, -1)) events.sort(keylambda x: (x[0], x[1])) cur 0 max_cur 0 for _, delta in events: cur delta max_cur max(max_cur, cur) return max_cur注意排序时同一时间点上要先处理结束事件-1再处理开始事件1保证“一个任务刚结束另一个任务马上开始”的情况下可以复用车辆。写成(x[0], x[1])排序就是让-1排在1前面。两种做法性能差不多但堆贪心更符合“调度”的直觉扫描线更符合“数学建模”的直觉。笔试时写出任何一种都能拿满分我建议选自己最熟悉的那种而不是在现场临时切换思路。5. 复盘这套题真正在选拔什么能力5.1 审题与建模是笔试的分水岭把这三道题放在一起看会发现一个共同点没有一道题把算法名字写在题目里。区间合并被写成了“统计覆盖总时长”拓扑排序被写成了“输出模块启动顺序”堆贪心被写成了“最少需要多少辆测试车”。很多人考完抱怨说“题目读不懂”本质上不是语文问题而是缺少把业务描述抽象成数据结构的训练。我自己的经验是拿到一道场景化算法题先不要急着写代码用两分钟在草稿纸上画出三样东西输入是什么输出是什么中间要维护什么样的数据结构。比如第一题输入是区间列表输出是总长度中间要维护的是“当前合并区间”第二题输入是图输出是线性序列中间要维护的是“入度为0的节点集合”。模型一旦确定后面就是默写模板。5.2 代码规范和自测习惯比想象中重要笔试的判题系统不会因为你的代码风格好看给分但自测习惯绝对会影响分数。三道题里第一题如果不处理空输入样例可能直接崩第二题如果建的图方向反了样例输出完全对不上第三题如果排序时没处理同时间点的结束和开始顺序边界数据就会错。我后来带人准备笔试时反复强调一个自查清单输入为空时我的代码是否还能跑最极端情况所有区间重叠 / 完全不重叠 / 完全包含是否输出符合预期题目里的“相接算不算重叠”“结束时间和开始时间相同时能不能复用”这类细节确认了吗数据规模是10^5还是10^9如果是后者O(n^2)的解法直接淘汰。这套题的三道题数据规模都指向O(n log n)解法真有人上来用O(n^2)的暴力扫描做第一题在小数据上可能看不出来问题但大数据一定超时。5.3 给准备自动驾驶公司校招的同学三个建议如果你现在正在准备自动驾驶公司算法岗的校招以这套题和后续我参加面试的经验给你三个实操性很强的建议把LeetCode中等题刷到“闭着眼睛能默写”的程度。区间合并、拓扑排序、会议室这类题属于高频考点每年换个业务包装反复出现。不要只满足于AC要能把边界条件原原本本说出来。练习场景题建模。看到任何题目不管它讲的是车还是外卖还是直播先尝试用“输入-数据结构-输出”框架拆解。这个能力不只在笔试有用在后面的技术面、HR面聊项目时都会成为加分项。多写Python代码但要注意性能细节。自动驾驶公司笔试不少支持Python但Python的递归深度、大常数都很吃亏。能用迭代就不用递归能用数组模拟的优先队列就别手写堆这些细节会在关键时刻帮你省下调试时间。最后分享一个我自己踩过的坑。当年做第一题时我把相接区间算成了不重叠导致输出和预期结果差了一小节检查了很久才发现是自己对题目里“覆盖”的理解有偏差。后来我养成了一个习惯任何一道区间类题目动笔前先问自己三个问题——区间是开还是闭相接算不算重叠输出要的是合并后的区间还是只需要长度这三个问题弄明白了区间题基本不会出错。这套真题我后来又刷过几遍每次重新做都会有新的体会面试和实际工作中处理时间窗口、任务调度这些问题时当年的基础帮了大忙。