最近在整理自动驾驶公司算法岗的校招笔试题翻到小马智行 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 - xidy 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 ADOBECODEBANCt 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(keylambda 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的样例检查一遍第四笔试环境没有自动补全写代码时变量名尽量短且一致减少打字错误。准备校招笔试不是冲刺几天就能搞定的事但像小马智行这套题把高频算法和真实业务结合得这么紧密的案例其实不多。你能把这套题吃透就说明不只是在背题而是真的理解了算法背后的工程含义。后面就算遇到新题也能更快地找到解题方向。最后再分享一个小技巧我每次笔试复盘时会专门把“当时卡住的知识点”和“没考虑到的边界条件”单独记录在一个文档里隔一周再看一遍。刷题和健身一样肌肉记忆需要反复刺激把自己犯过的错变成下一轮复习的起点比盲目刷十道新题更高效。希望这篇真题解析能帮你少走一些弯路。