自动驾驶算法岗笔试题解析：哈希表、滑动窗口与区间合并

最近在整理自动驾驶公司算法岗的校招笔试题，翻到小马智行 pony.ai 的2019校招真题（二）时，发现这套题放在今天看依然很有代表性。它没有太偏门的题目，三题全是面试笔试里最高频的考点：哈希表处理几何问题、滑动窗口解决子串覆盖、排序加贪心合并区间。但难得的是，每道题都能往自动驾驶的工程场景上靠，比如激光雷达点云共线、地图文本匹配、传感器时间区间合并，考的不是死记硬背，而是能不能把算法转化成工程实现。

这篇文章我就按“真题回顾 -> 思路推导 -> 代码实现 -> 场景延伸”的顺序，把这套题完整拆一遍。不管你是正在准备自动驾驶算法岗校招，还是想补一补这几类高频算法的底子，这套题都值得认真吃透。尤其是第二题和第三题，代码量不大，但边界条件特别多，笔试现场很容易翻车，我会把容易踩的坑也一起点出来。

1. 这套题到底在考什么

1.1 小马智行笔试风格与岗位定位

小马智行是搞 L4 级自动驾驶的公司，算法岗和软件岗的笔试风格一直比较务实。2019 年那会儿，公司正在快速扩充团队，笔试题目没有走偏难怪路线，而是把校招候选人必须具备的几项基本功拿出来考：数据结构基础、代码实现速度、边界条件敏感度、复杂度分析能力。

这套真题（二）里没有出现复杂的机器学习公式，也没有让人写一个卷积网络前向传播，而是三道纯算法题。这说明在自动驾驶公司看来，算法岗候选人首先要具备扎实的编程功底。模型可以入职后再学，但连哈希表、指针、排序都写不利索，后面的工程协作和数据 pipeline 开发会非常吃力。所以不管是感知组、规划组还是地图组，笔试第一关都会用这类题目来筛人。

从题目难度看，这套题属于中等偏上。第一题需要想到用最大公约数化简斜率，第二题需要掌握滑动窗口的“先扩展、再收缩”框架，第三题要能快速证明排序贪心的正确性。这三类题在 LeetCode 上都有对应原题或变种，但把原题包装成自动驾驶场景后，很多候选人容易在题目理解上多花时间，从而影响后续答题节奏。

1.2 三道题的知识点分布与场景映射

我把这三道题的核心信息整理成了一张表，方便你直观感受它们的考察维度。

从表格能看出，三道题覆盖了“哈希、双指针、排序”这三大基础算法模块。这也是我建议大家在校招准备期重点投入的部分。小马智行的笔试不会直接考“请你描述一下 A* 算法的伪代码”，而是把 A* 拆解成更基础的图论和数据结构题，比如网格最短路径的变种。你只有把基础题刷熟，才能在有时间压力的情况下完成变形题的推导。

2. 真题一：点云共线，平面上最多有多少个点在同一条直线上

2.1 题目回顾与理解

题目大意是：给定二维平面上的 n 个点，每个点用坐标 (x, y) 表示，求最多有多少个点位于同一条直线上。例如输入[[1,1],[2,2],[3,3]]，输出 3；输入[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]，输出 4。

这类问题在自动驾驶里很常见。激光雷达扫到一帧点云后，路沿、车道线、墙面这些物体都可以看成由大量共线点组成的几何结构。如果能在点云中快速找出一组共线点，就能辅助后续的直线拟合和特征提取。笔试不会直接让你写点云处理库，但会把问题抽象成这样一个数学题，考察你对几何规律和哈希表的掌握。

2.2 从暴力到哈希的推导

最直接的想法是枚举任意两个点，确定一条直线，再统计其他点是否在这条直线上。三个点共线的判断条件是用斜率相等，也就是(y2 - y1) / (x2 - x1)相等。但直接枚举两点再遍历所有点，时间复杂度是 O(n^3)，笔试中 n 可能到几千，这个复杂度必挂。

换一个角度：如果固定一个点 i，那么所有与点 i 共线的点，它们与点 i 构成的斜率一定相同。于是问题就变成了：对每个点 i，用哈希表统计它到其他点的斜率出现次数，出现次数最多的那个斜率，加上点 i 本身，就是“经过点 i 的直线上最多有多少个点”。整体再扫一遍所有 i，取最大值即可。这样时间复杂度降到 O(n^2)，空间复杂度 O(n)，是笔试能接受的方案。

2.3 用最大公约数表示斜率，避免浮点精度问题

既然要用斜率作为哈希表的 key，最直接的想法是存浮点数，比如dy / dx。但在笔试里这是大忌。浮点数的精度问题会导致原本在同一条直线上的点因为计算误差被分到不同的 key 里，更麻烦的是斜率无穷大的垂直线没法用普通浮点数表示。

正确做法是用最简分数来表示斜率。具体来说，对点 i 和点 j，计算dx = xj - xi，dy = yj - yi，然后同时除以 dx 和 dy 的最大公约数，得到(dx', dy')。如果dy' / dx'相同，这两个分数一定相同，哈希就不会出错。这里还需要做方向归一化：允许 dx 为负会导致相反方向出现两个 key，所以统一约定 dx 必须非负；如果 dx 为 0，则规定 dy 为正。这样同一条直线上的点，无论从哪个方向计算，得到的 key 都是一样的。

2.4 代码实现

我按照上面的思路写了一份 Python 实现，比 C++ 版本更直观，适合笔试时快速过流程。

from math import gcd from collections import defaultdict def max_points(points): n = len(points) if n <= 2: return n ans = 0 for i in range(n): slopes = defaultdict(int) same = 1 local_max = 0 for j in range(i + 1, n): dx = points[j][0] - points[i][0] dy = points[j][1] - points[i][1] # 完全重合的点，后面统一加到结果里 if dx == 0 and dy == 0: same += 1 continue g = gcd(abs(dx), abs(dy)) dx //= g dy //= g # 方向归一化，避免 -1/2 和 1/-2 被当成不同斜率 if dx < 0 or (dx == 0 and dy < 0): dx = -dx dy = -dy key = (dx, dy) slopes[key] += 1 local_max = max(local_max, slopes[key]) ans = max(ans, local_max + same) return ans

这段代码的核心是两处：一是用gcd化简斜率，二是归一化方向。same用来统计与基准点重合的点，它们可以出现在任何一条经过基准点的直线上，所以最终结果要加上same。如果不考虑重合点，很可能会漏计。

2.5 边界条件与笔试易错点

这道题的易错点非常集中。第一，忘记处理重复点。现实点云数据里两个点坐标完全一样是有可能的，笔试用例也专门挖了这种坑。第二，斜率方向没归一化。比如 dx 为 1、dy 为 -2 和 dx 为 -1、dy 为 2 其实是一条直线，如果不归一化就会统计成两个 key。第三，gcd里的 abs 不能省，否则负数的最大公约数会出现负值，导致 key 不统一。

还有一个细节是枚举时基准点的选择。很多人的第一个版本会一不小心算得太重：对每条直线统计两次。我的做法是固定外层的基准点 i，只枚举 j > i，这样每个点对只用一次。虽然时间复杂度还是 O(n^2)，但常数更小，代码也更清晰。笔试现场如果时间紧张，这个细节能帮你省下不少调试时间。

3. 真题二：最小覆盖子串，从滑动窗口到地图文本检索

3.1 题目回顾

题目大意是：给你一个字符串 s 和一个字符串 t，在 s 中找到包含 t 的全部字符的最短子串。如果不存在，返回空字符串。比如s = "ADOBECODEBANC"，t = "ABC"，满足条件的最短子串是"BANC"。注意 t 中可能出现重复字符，子串中对应字符的数量必须不少于 t 中的数量。

这道题初看和自动驾驶八竿子打不着，但仔细想，地图采集回来的文本数据、路况描述日志、用户搜索关键词匹配都会用到类似问题。比如在大量地图 POI 描述中，你想找到同时包含“充电站”和“停车场”这两个关键词的最短文本片段，就是一个典型的“最小覆盖子串”变种。理解了底层算法，后续换个壳你也能识别出来。

3.2 滑动窗口双指针思路

暴力解法是枚举所有子串，判断是否覆盖 t，时间复杂度 O(n^3)，完全不可行。正确解法是滑动窗口，也叫双指针。

具体做法是维护两个指针 left 和 right，先不断向右移动 right，扩展窗口，直到窗口内包含了 t 的所有字符。此时记录窗口长度，然后尝试向右移动 left，收缩窗口，如果收缩后仍然覆盖 t，就继续记录更短的窗口；一旦不满足覆盖条件，就停止收缩，再次移动 right 扩展窗口。整个过程 left 和 right 都只向右移动，每个字符最多被访问两次，时间复杂度 O(n)。

实现时不需要真的去比较每个字符数量，而是可以用一个need字典记录 t 中每个字符还缺多少个，再维护一个missing变量记录当前窗口还缺少的字符总数。当missing == 0时，说明窗口已经满足覆盖条件，可以开始收缩左边界。

3.3 代码实现

这里我给出一个简洁的 Python 版本，核心是need字典和missing变量的配合。

def min_window(s: str, t: str) -> str: from collections import Counter need = Counter(t) missing = len(t) left = 0 start = 0 min_len = float('inf') for right, ch in enumerate(s): # 当前字符是 t 中缺失的字符时，missing 减一 if need[ch] > 0: missing -= 1 need[ch] -= 1 # 窗口已经覆盖 t 的所有字符，开始收缩 while missing == 0: if right - left + 1 < min_len: min_len = right - left + 1 start = left left_ch = s[left] need[left_ch] += 1 if need[left_ch] > 0: missing += 1 left += 1 return s[start:start + min_len] if min_len != float('inf') else ""

这段代码不容易一次写对的原因在于：need[ch]的值可能是负数。当窗口中出现很多个 t 里没有的字符时，它们的need会变成负数，但这不影响missing。只有当need[left_ch]从 0 变回 1 时，才说明左边界丢掉的字符是 t 正需要的，此时missing才需要加一。我在笔试现场第一次写时就在这里翻过车，把missing的自增条件写成了need[left_ch] >= 0，结果窗口收缩时多算了很多无效字符。

3.4 工程场景延伸

别觉得这道题只是刷题，它在搜索引擎和文本处理里非常实用。小马智行的地图链路里，需要处理海量的高精地图日志和路况描述。如果系统要在日志中提取包含多个关键词的最短上下文，就可以直接套用这个算法。

另外，这道题还有一个常见变种：允许字符顺序保持原样，但要找最短覆盖子序列。那个就难很多了，需要用动态规划或预处理索引。但笔试考的通常是最短覆盖子串，滑动窗口就够了。我建议你把这个“先扩展、再收缩”的框架吃透，因为后续很多题，比如“字符串排列”“最长无重复子串”“K 个不同字符的最长子串”，都是同一个骨架换参数。

3.5 常考变形与扩展

小马智行这类公司出题喜欢在一道题的基础上再加一层变化。比如把字符串字符集限定为英文字母，简化成用定长数组做计数；再比如要求返回覆盖子串的个数而不是具体子串。遇到这些变形，你只要记住滑动窗口的核心是维护一个“当前窗口是否满足条件”的状态，并且让这个状态在指针移动时能以 O(1) 代价更新，就不会慌。

如果 t 的长度远大于 s，可以先做一步预处理：只保留 s 中出现在 t 里的字符，组成一个新的索引序列，再跑滑动窗口。这样能显著减少无效字符的移动次数。笔试时虽然不强制要求，但主动做这一步能体现你的工程优化意识。

4. 真题三：合并区间，简单的排序贪心其实有讲究

4.1 题目回顾

题目大意是：给定一组区间intervals，每个区间用[start, end]表示，合并所有重叠的区间，返回不重叠区间的数组。例如输入[[1,3],[2,6],[8,10],[15,18]]，输出[[1,6],[8,10],[15,18]]。

这道题表面上是纯数组操作，为什么会被放进小马智行的笔试题？这就要说到自动驾驶里的时间同步问题了。一辆车上十几个传感器，每个传感器各自记录数据，每一帧数据都会带一个时间戳区间。当你想把多传感器的数据融合到一个时间轴上时，首先要做的是合并时间上重叠的区间。合并完以后，才能判断哪些帧可以同时用于感知融合，哪些帧之间有间隙需要插值补偿。

4.2 排序加贪心的正确性

合并区间的经典解法是先按区间起点排序，然后顺序扫描，维护当前已经合并到的区间右端点。如果下一个区间的起点大于当前右端点，说明两个区间不重叠，把当前区间保存下来，开始新的合并；否则，更新当前右端点为两者中的较大值。

为什么要先排序？因为只有按起点排序后，才能保证任意两个不连续的重叠区间在被扫描到时已经相邻，这样一遍扫描就能完成所有合并，而不用反复回看。排序的复杂度是 O(n log n)，扫描的复杂度是 O(n)，整体 O(n log n)，这是区间合并能达到的最优复杂度。如果手动维护并查集，也能合，但编码复杂度高，笔试阶段完全没必要。

需要证明的一点是：排序后，如果后一个区间的起点小于等于当前右端点，那么它一定与当前已合并区间重叠，可以直接并入。这个结论可以从当前区间的定义出发证明：当前区间是所有已扫描区间合并后的结果，它的右端点是已扫描部分的最远右端点。后一个区间的起点一旦不超过这个端点，就必然与当前合并区间有交集。

4.3 代码实现

Python 实现非常短，但短代码不代表容易写对。

def merge(intervals): intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # 当前合并区间为空，或新区间起点在合并区间右端点之后 if not merged or merged[-1][1] < interval[0]: merged.append(list(interval)) else: merged[-1][1] = max(merged[-1][1], interval[1]) return merged

这个版本的关键判断是merged[-1][1] < interval[0]。注意这里用的是严格小于。如果新区间的起点等于当前右端点，比如[1,3]和[3,5]，两个区间在端点 3 处接触。按照题目通常定义，端点接触也属于重叠，应该合并成[1,5]。所以不能写成<=，否则会把正好相接的区间错误地拆成两个。

另一个容易错的地方是直接用interval本身而不拷贝。intervals里的元素可能是元组或任何不可变类型，如果后续需要修改合并后的右端点，直接赋值会出问题。所以我在 append 时特意用了list(interval)，确保 merged 里的区间是可变的。笔试时如果输入是列表，直接interval[:]也可以。

4.4 自动驾驶场景：时间区间合并

再看传感器数据融合的场景。假设你拿到三路摄像头和一路激光雷达的时间戳区间，手动合并这些区间后，你会得到几个不重叠的时间窗口。每个窗口代表所有传感器都能覆盖到的一段时间，在这个窗口内做融合，数据是最齐整的。窗口之间的间隙就代表某些传感器存在丢帧或时间不同步，需要做插值或等待下一帧。

这道题在面试追问里还有一个常用的变形：给你一堆区间，求这些区间中重叠次数最多的位置。这个问题可以直接套用“差分数组”或“扫描线”技巧，在自动驾驶里对应“在哪个时间点同时有多少个传感器上报数据”，用于评估系统并发负载。建议你在写完合并区间后，顺手把差分数组也复习一遍，因为小马智行很喜欢在同一场笔试里出这类相关但更进一步的题。

4.5 变种与复杂度对比

我遇到过不少候选人对合并区间很熟，但一旦把区间变成“带权值的时间段”，需要合并后同时累加权重，就不知道如何下手。其实核心还是排序加扫描，只是额外维护一个权重和。这说明刷题不能只背代码，要理解每一步在维护什么状态。合并区间维护的是“当前已扫描区间的并集”，任何变种都是在并集上增加额外信息。

与并查集解法相比，排序贪心更适合区间合并，因为并查集需要先离散化，再处理大量区间关系，代码复杂度高。只有当区间数量特别大、排序代价高到不可接受时，才会考虑其他做法。校招笔试不追求最优到极致，正确、清晰、可维护的代码才是拿分关键。

5. 复盘与备战建议

5.1 笔试时间分配

这套真题（二）三道题，我建议的时间分配是：第一题 25 分钟，第二题 20 分钟，第三题 15 分钟，剩下时间留给调试和检查边界条件。实际笔试中，很多人会在第一题上卡太久，因为斜率归一化这个点想不到，导致 O(n^3) 暴力写完，样例过了但大数据量用例直接超时。

如果你遇到一道题超过 15 分钟没有任何思路，不要继续死磕，先跳到后面容易拿分的题。笔试分数看的是总通过用例数，不是单题满分。我见过很多实力不错的候选人因为第一题卡住，后面两道简单题都没时间写，非常可惜。

5.2 刷题优先级

结合小马智行和其他自动驾驶公司的笔试风格，我建议按以下优先级刷题：首先是哈希表与数组，包括两数之和、三数之和、最长连续序列、字母异位词分组；其次是双指针与滑动窗口，包括无重复字符的最长子串、最小覆盖子串、字符串排列、找到字符串中所有字母异位词；然后是排序与贪心，包括合并区间、插入区间、会议室 II、用最少数量的箭引爆气球；最后是图论与搜索，包括岛屿数量、课程表、网络延迟时间、单词接龙。

如果你还有时间，BFS/DFS 和 Dijkstra 一定要熟。自动驾驶路径规划里最基础的算法就是图搜索，很多公司的笔试会直接考网格地图的最短路径，看起来像 BFS 模板题，实际上是在考状态设计能力，比如如何定义“位置 + 方向 + 速度”这样的状态节点。

5.3 实战心得与避坑清单

我从这套题里总结了一条核心经验：做题前先想清楚“这道题在真实工程里对应什么操作”。小马智行这类公司出题不是单纯为了考察刷题量，而是在通过题目判断你有没有把数学、数据结构和工程问题搭桥的能力。比如看到点云共线，你能想到哈希表加最简分数；看到区间合并，你能想到传感器时间同步，这些联想本身就会体现在你的答题注释里，面试官一眼就能看出来。

避坑清单我再列几条，都是亲身踩过的：第一，任何涉及浮点数比较的题，优先考虑用整数分数表示；第二，滑动窗口的 missing 条件要画一个小例子验证一下，尤其在窗口左边界移动时；第三，区间合并的边界情况要用start == end的样例检查一遍；第四，笔试环境没有自动补全，写代码时变量名尽量短且一致，减少打字错误。

准备校招笔试不是冲刺几天就能搞定的事，但像小马智行这套题，把高频算法和真实业务结合得这么紧密的案例其实不多。你能把这套题吃透，就说明不只是在背题，而是真的理解了算法背后的工程含义。后面就算遇到新题，也能更快地找到解题方向。

最后再分享一个小技巧：我每次笔试复盘时，会专门把“当时卡住的知识点”和“没考虑到的边界条件”单独记录在一个文档里，隔一周再看一遍。刷题和健身一样，肌肉记忆需要反复刺激，把自己犯过的错变成下一轮复习的起点，比盲目刷十道新题更高效。希望这篇真题解析能帮你少走一些弯路。