小马智行算法真题复盘：车辆调度、轨迹压缩与数据流中位数

最近整理旧电脑里的笔记翻到2019年刷小马智行pony.ai校招真题二时的记录。那年自动驾驶赛道正热pony.ai 的笔试在圈里一直以“题不算偏但很能看出候选人思维习惯”著称。我当时投的是算法岗把能搜集到的真题都刷了一遍尤其是这一套二题目风格和常规 LeetCode 有明显区别每道题都裹了一层自动驾驶业务场景但扒开外衣后核心还是数据结构加算法的硬功夫。这篇文章我就把这套题里的三道典型题目完整复盘一遍从题目还原、解题思路到代码实现、现场踩坑都聊透给准备自动驾驶方向算法面试的同学一个参考。1. 真题概况小马智行算法岗在校招里到底考什么1.1 三个考察维度和一个隐藏前提先说结论pony.ai 这类 L4 自动驾驶公司的算法岗笔试筛选的不只是“会不会写代码”而是“在真实业务约束下能不能把问题建模清楚”。这套真题二给我的整体感觉是三个维度第一是数据结构功底堆、栈、哈希、递归这些基础工具要非常熟练第二是算法优化意识暴力解法写在纸上谁都会关键是能不能主动想到贪心、分治、双堆这类更优方案第三是业务敏感度题目会穿上自动驾驶的外衣比如车辆调度、GPS轨迹、传感器数据流如果完全不了解场景很容易被题干绕进去。还有一个隐藏前提容易被忽略笔试时间通常只有 90 到 120 分钟题量大约 3 到 4 道这意味着每道题留给你从读题到调通的时间只有 30 分钟左右。想在这么短的时间内写出无 bug 的高质量代码光靠临场发挥是不够的必须提前把常见模型练成条件反射。所以我复盘这套题的目的很简单让你看清题目背后的本质考点下次遇到类似的场景化包装能一眼识别出它到底在考什么。1.2 这组真题涵盖的算法点这套真题二里的三道题恰好覆盖了三个不同方向的经典问题题目业务场景包装核心考点难度测试车辆调度多辆自动驾驶测试车排期贪心 最小堆 / 差分数组中等GPS轨迹压缩传感器轨迹点抽稀分治 / 计算几何中等偏上传感器数据流中位数多路数据流实时统计双堆 / 有序容器中等这三类问题在校招面试中出现频率极高而且都有很强的扩展性。比如车辆调度本质上就是区间重叠问题轨迹压缩就是经典的道格拉斯-普克算法数据流中位数则是堆结构的典型应用。下面我按顺序逐题拆解。2. 真题一自动驾驶测试车辆调度最小车辆数2.1 题目还原与问题转化先还原一下题目大意某自动驾驶测试场需要执行 n 个路测任务每个任务有一个开始时间 start 和一个结束时间 end一辆测试车同一时刻只能执行一个任务问最少需要多少辆测试车才能完成所有任务。输入是一堆时间区间输出是一个整数。这道题的场景外衣很容易让人想到复杂的“车辆调度系统”但其实把它剥开就是一个很纯粹的区间问题给定 n 个左闭右开区间 [start, end)求同一时刻最多有多少个区间重叠。为什么呢因为每个重叠的区间都需要一辆单独的车来执行重叠数的最大值就是车辆数的下界而只要车辆数足够覆盖最大重叠数通过适当的任务分配一定可以排得开所以最少车辆数就等于最大重叠数。这里有个小细节题目里的区间开闭会影响代码判断。我建议统一按左闭右开处理即任务在 end 时刻已经结束、车辆可用。这样一辆车在 t 时刻空出来另一个同样从 t 开始的任务就可以接上符合实际场景。如果你习惯闭区间代码里的判断条件要相应调整面试时主动和面试官确认这一点会加分。2.2 贪心加最小堆从会议安排到车辆调度最直接的做法是贪心加分堆。先把所有任务按开始时间从小到大排序然后维护一个小顶堆来记录当前正在使用的每辆车的最早空闲时间。遍历每个任务时先看堆顶那辆车的空闲时间如果堆顶时间小于等于当前任务的开始时间说明这辆车已经空出来了直接弹出然后把当前任务的结束时间放入堆中代表这辆车在结束时间之前被占用。遍历结束后堆的大小就是最少需要的车辆数。int minVehicles(vectorpairint, int tasks) { sort(tasks.begin(), tasks.end()); // 按开始时间排序 priority_queueint, vectorint, greaterint pq; // 小顶堆存每辆车的空闲时间 for (auto task : tasks) { int start task.first, end task.second; if (!pq.empty() pq.top() start) { pq.pop(); // 最早空闲的车可以复用 } pq.push(end); } return pq.size(); }每次插入和弹出堆的时间复杂度都是 O(log n)排序是 O(n log n)整体 O(n log n)。空间复杂度 O(n)。这里的关键点在于为什么取堆顶弹出是正确的因为堆顶是当前所有车里最早空闲的一辆如果它都没法复用其他车更不可能复用反过来如果它能复用选择它一定不会让结果变差这就是贪心选择性质的直观解释。你可以试着用反证法证明面试时说出来会显得思路很完整。2.3 另一种思路差分数组求最大重叠数除了堆方法还有一个更轻量级的思路差分数组。因为最大重叠数就是同一时刻被占用的车辆数我们可以在时间轴上做标记。遍历所有区间在开始时间位置加 1在结束时间位置减 1然后从左到右做前缀和前缀和的最大值就是答案。int minVehiclesByDiff(vectorpairint, int tasks, int maxTime) { vectorint diff(maxTime 1, 0); for (auto task : tasks) { diff[task.first] 1; diff[task.second] - 1; } int cur 0, ans 0; for (int i 0; i maxTime; i) { cur diff[i]; ans max(ans, cur); } return ans; }差分数组的优点是实现简单、时间复杂度 O(n T)其中 T 是时间轴长度。缺点是如果时间范围很大比如时间戳精确到毫秒的 64 位整数就没法开数组了这时需要改用有序容器离散化。面试时建议先给出堆解法再补充差分数组作为对比展示你思路的广度。实际业务里测车排期的数据量通常在几千到几万级别时间戳跨度大所以堆解法更通用。2.4 这道题的边界与加分回答这道题我当年做的时候踩了一个坑把任务结束时间当成左闭右闭区间处理导致结束时间和开始时间相同的任务没有正确复用车辆结果多算了一辆。后来总结出几个必须考虑的边界情况空输入返回 0只有一个区间返回 1所有区间互不重叠时返回 1所有区间完全重叠时返回 n区间结束时间恰好等于另一个区间开始时间时应该能复用同一辆车。还有一个加分项你可以主动和面试官讨论“如果每辆车有固定的启动准备时间怎么办”。比如任务结束后需要 10 分钟做车辆检查才能跑下一个任务那判断条件就变成 pq.top() 10 start。这种举一反三的讨论在面试里非常加分因为它说明你不是在背题而是真的理解了模型的可扩展性。3. 真题二GPS轨迹压缩道格拉斯-普克算法3.1 为什么自动驾驶要压缩轨迹点第二题是一个计算几何问题车辆在道路上行驶车载系统每隔一小段时间记录一个 GPS 轨迹点一天下来会产生几万个点。这些点直接存储和传输都很浪费而且 GPS 本身有噪声很多点其实没什么信息量。题目要求设计一个算法在保证压缩后轨迹与原轨迹偏差不超过阈值 epsilon 的前提下尽可能少地保留点。这道题背后的业务逻辑非常真实。自动驾驶系统在采集路测数据时高精地图采集车一天能产生海量的轨迹点如果不对原始 GPS 数据做抽稀处理存储成本和回传带宽都扛不住。但压缩又不能太粗暴否则会丢掉重要的道路形状信息比如弯道、匝道口的细节。所以需要在“压缩率”和“保真度”之间找平衡这正是道格拉斯-普克Douglas-Peucker算法的应用场景。3.2 算法核心递归找最远点道格拉斯-普克算法的思路很直观一句话概括不断找离首尾连线最远的点如果这个点的距离超过了阈值就保留它并递归处理两侧如果没超过中间的整段点都可以丢弃。具体流程是这样的对于一条轨迹段 [start, end]把 start 和 end 连成一条线段。遍历中间所有点计算它们到这条线段的垂直距离记录最大距离和对应的点索引。如果最大距离小于等于 epsilon说明这段轨迹用一条直线代替也不会偏差太大所有中间点全部丢弃。如果最大距离大于 epsilon说明当前点是一个“关键转折点”必须保留然后分别对 [start, mid] 和 [mid, end] 两段递归执行同样的操作。void dpCompress(const vectorPoint pts, int l, int r, double eps, vectorbool keep) { if (r - l 2) return; // 区间内没有中间点 double maxDist 0; int idx -1; for (int i l 1; i r; i) { double d pointToSegmentDist(pts[i], pts[l], pts[r]); if (d maxDist) { maxDist d; idx i; } } if (maxDist eps) { keep[idx] true; dpCompress(pts, l, idx, eps, keep); dpCompress(pts, idx, r, eps, keep); } }算法结束后keep 为 true 的点就是压缩后保留的关键点。递归深度在最坏情况下可能达到 O(n)如果轨迹点特别多要注意栈溢出的问题实际工程里可以改成显式栈迭代实现。3.3 点到线段距离怎么算才正确这个算法最容易被忽视的坑在于计算的是点到线段的距离不是点到直线的距离。如果直接用点到直线距离公式当一个点的投影落在首尾连线之外时计算结果会偏大导致该保留的点没保留或者该丢弃的反被保留压缩出来的轨迹会有明显偏差。点到线段距离的计算分三步先把首尾点记为 a、b把当前点记为 p计算向量 ab 与 ap 的点积得到比例参数 t如果 t 小于 0距离就是 p 到 a 的距离如果 t 大于 1距离就是 p 到 b 的距离如果 t 在 0 到 1 之间距离就是 p 到投影点的距离。double pointToSegmentDist(const Point p, const Point a, const Point b) { double dx b.x - a.x, dy b.y - a.y; if (dx 0 dy 0) return dist(p, a); double t ((p.x - a.x) * dx (p.y - a.y) * dy) / (dx * dx dy * dy); if (t 0) return dist(p, a); if (t 1) return dist(p, b); Point proj {a.x t * dx, a.y t * dy}; return dist(p, proj); }面试时如果能把“为什么不能直接用点到直线距离”讲清楚面试官基本就能确认你是真的懂这个算法而不是背了模板。我当年就在这里被追问过一次当时大脑短路说了“差不多”被面试官提醒后才发现投影点可能落在线段延长线上属于非常典型的翻车现场。3.4 压缩率、阈值和工程实现细节道格拉斯-普克算法的时间复杂度最坏情况下是 O(n²)比如轨迹点形成一个非常规则的锯齿形状每次递归都几乎遍历整段。平均情况下接近 O(n log n)实际道路轨迹数据用起来性能还是可以接受的。如果数据量达到百万级可以先用均匀采样缩小规模再做 RDP 压缩牺牲一点点精度换取性能提升。阈值 epsilon 的选择直接影响压缩效果。epsilon 太小保留点太多压缩率上不去epsilon 太大弯道形状会被拉直影响后续地图匹配精度。实际项目中一般根据业务需求定比如高精地图生产要求误差控制在 20 厘米以内那 epsilon 就只能设 0.2 米做可视化预览的话可以放宽到 2 到 5 米。还有一个细节GPS 点本身有噪声设定 epsilon 时要大于传感器噪声的均方根误差否则压缩算法会把噪声当成有效特征点保留下来反而起不到降噪的目的。4. 真题三多路传感器数据流维护中位数4.1 题目背景与限制条件第三题换了个场景自动驾驶车辆上有激光雷达、摄像头、毫米波雷达等多路传感器每路传感器都在持续产生数据。我们需要实时维护当前所有数据的中位数用来做统计分析和异常检测。数据不断追加要求每次插入新数据后都能高效得到中位数。这个场景的本质是一个在线数据流问题。如果数据量小最笨的办法是每来一个数就排序取中间值但这样每次插入的复杂度是 O(n log n)显然不行。如果用数组维护有序序列插入要 O(n) 位移也不行。这道题考的就是一个非常经典的数据结构组合最大堆加最小堆俗称双堆法。4.2 双堆解法最大堆加最小堆思路是这样的维护两个堆最大堆 maxHeap 存数据流中较小的一半最小堆 minHeap 存较大的一半并且保证两堆大小之差不超过 1。这样中位数就只和两个堆顶有关。插入新数时先判断如果当前最大堆为空或者新数小于等于最大堆堆顶就放进最大堆否则放进最小堆。插入后检查两个堆的大小关系如果最大堆比最小堆大超过 1把最大堆堆顶搬到最小堆如果最小堆比最大堆大把最小堆堆顶搬到最大堆。这样始终保持 maxHeap.size() minHeap.size() 或 maxHeap.size() minHeap.size() 1。查询中位数时如果两堆大小相等中位数是两个堆顶的平均值如果最大堆多一个中位数就是最大堆的堆顶。priority_queueint maxHeap; // 较小的一半堆顶是较大的一半里最大的 priority_queueint, vectorint, greaterint minHeap; // 较大的一半 void addNum(int x) { if (maxHeap.empty() || x maxHeap.top()) { maxHeap.push(x); } else { minHeap.push(x); } if (maxHeap.size() minHeap.size() 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } else if (minHeap.size() maxHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { if (maxHeap.size() minHeap.size()) { return (maxHeap.top() minHeap.top()) / 2.0; } return maxHeap.top(); }插入操作的时间复杂度为 O(log n)查询中位数为 O(1)空间复杂度 O(n)。这个方案的优点是稳定且容易实现是数据流中位数问题的标准答案。面试官如果追问“数据量特别大内存放不下怎么办”可以答分布式场景下用分段直方图估算近似中位数或者用布隆过滤器配合采样但一般来说能写到双堆这步就已经过关了。4.3 扩展问题滑动窗口内中位数我在现场被追问过一个扩展如果中位数不是在全量数据流上算而是最近 M 个数据点里算怎么办这时候双堆就不好使了因为堆不支持按值删除非堆顶元素。一个方案是改成“懒删除”每来一个新数正常插入双堆同时把要移出窗口的数标记为待删除查询中位数前先把堆顶那些已经被标记删除的数全部弹出再调整两堆平衡。这样写起来比想象中复杂容易出错。更稳妥的方案是直接用平衡树C 的 multiset 或 Java 的 TreeMap维护一个固定大小为 M 的有序窗口。每次插入新数、删除旧数都是 O(log M)取中位数用迭代器 O(1) 搞定。面试时先说双堆再主动提滑动窗口场景下改用平衡树会显得你有工程视野而不是只会背一道题。4.4 面试时如何从暴力推导到最优解这类数据流问题面试官通常更看重你推导答案的过程而不是直接甩最优解。我当时在面试中的表达顺序是先说暴力方案每来一个数插入数组排序取中间值复杂度 O(n log n)不用写代码然后说“内存里维护一个有序数组插入用二分找位置再移位查询 O(1) 但插入 O(n)数据量大了会超”接着说“平衡树可以做到 O(log n) 插入和 O(1) 查询中位数但实现复杂”最后引出双堆方案写代码。这种从暴力到优化的递进式表达能让面试官看到你分析问题的完整链路比直接写最优解更有说服力。代码写完之后最好再主动补充一句“这个题也可以用 multiset 实现”虽然现场不一定让写但这句话会成为额外的加分项。5. 复盘与实战建议校招算法面试怎么准备5.1 我踩过的坑和见过的失误刷这套题的时候我总结了不少同龄人常见的失误。第一个就是审题不清尤其像车辆调度这种有场景包装的题容易被“测试车”“路测任务”这些词带偏以为要设计什么复杂的调度系统结果忽略了本质是区间重叠。应对方法很简单读题时先用一句话把问题抽象成纯数据结构和算法的描述写在草稿纸上。第二个失误是在轨迹压缩题上死磕“点到直线的距离”完全没考虑投影点位置属于计算几何基本功不扎实。第三个失误更隐蔽写数据流中位数时忘记了数据流里可能有重复值导致边界判断错误。重复值处理其实很简单新数等于堆顶时统一放进最大堆或最小堆都可以只要保证两堆大小平衡即可但很多人在紧张状态下会忽略这个边界。最后还有时间分配问题有人在一道题上死磕 40 分钟后面两道题直接崩盘。我的经验是每道题最多 30 分钟15 分钟没思路就先用暴力方案写一版拿部分分再逐步优化。5.2 时间分配、沟通与代码风格笔试现场的时间分配我建议先快速扫三题把会做的、思路清楚的放在最前面不要按题号顺序死磕。如果第一眼看到某个题没有清晰思路给它分配的时间不要超过 20 分钟。写完一题后花 2 分钟自查边界条件比如空输入、单元素、重复值、最大数值范围这些是扣分重灾区。代码风格方面自动驾驶公司普遍对 C 要求较高我建议笔试尽量用 C 写因为 STL 的 priority_queue、vector、sort 用起来非常顺手而且底层原理面试官一清二楚。变量命名不要用 a、b、c 这种至少用 start、end、heap 这种语义明确的单词。函数命名也要清晰看到 minVehicles 就知道是求最少车辆数。代码里加一两行关键注释解释“为什么这里要弹出堆顶”面试官一眼就知道你思路清楚。准备阶段除了刷题还要熟悉常见的工程场景。自动驾驶算法面试的题目覆盖面很广像轨迹、地图、传感器、路径规划、多传感器融合这些相关场景都可能被包装成算法题。我的建议是按专题刷区间类问题、树和递归、堆和数据流、图论最短路、动态规划每个专题吃透 20 道经典题再做场景化包装的变形题基本功就扎实了。这套题还有一个特别值得玩味的地方三题从不同角度考察了同一个核心能力——把无序的现实问题转化成有序的数据结构问题。车辆调度需要排序加堆轨迹压缩需要递归处理有序序列数据流中位数本身就是维护两个有序序列的平衡。想清楚这一点你准备的就不是一道道孤立的题而是一整套解决“数据有序性”问题的方法论。掌握这个方法应付的不只是这一套真题而是这一整类面试问题。最后再分享一个实际经验笔试之后通常还会有一轮电话技术面面试官可能会直接从你刚才写的代码里挑一个细节深挖。比如轨迹压缩这道题面试官问过我“如果你的轨迹是一个环形的赛道首尾点怎么选”我当时的回答是先把环形轨迹拆成两个半环分别压缩。这种问题没有标准答案但如果你在做题时确实思考过算法的边界现场回答会非常自然。所以刷题的时候别只盯着 AC多问问自己“这个算法的前提假设是什么什么场景下不适用”这一层功夫到了面场上你会有种“这题我见过”的踏实感。