企业官网建设流程全解析

最近整理旧电脑里的笔记，翻到2019年刷小马智行（pony.ai）校招真题（二）时的记录。那年自动驾驶赛道正热，pony.ai 的笔试在圈里一直以“题不算偏，但很能看出候选人思维习惯”著称。我当时投的是算法岗，把能搜集到的真题都刷了一遍，尤其是这一套（二），题目风格和常规 LeetCode 有明显区别：每道题都裹了一层自动驾驶业务场景，但扒开外衣后核心还是数据结构加算法的硬功夫。这篇文章我就把这套题里的三道典型题目完整复盘一遍，从题目还原、解题思路到代码实现、现场踩坑都聊透，给准备自动驾驶方向算法面试的同学一个参考。

1. 真题概况：小马智行算法岗在校招里到底考什么

1.1 三个考察维度和一个隐藏前提

先说结论：pony.ai 这类 L4 自动驾驶公司的算法岗笔试，筛选的不只是“会不会写代码”，而是“在真实业务约束下能不能把问题建模清楚”。这套真题（二）给我的整体感觉是三个维度：第一是数据结构功底，堆、栈、哈希、递归这些基础工具要非常熟练；第二是算法优化意识，暴力解法写在纸上谁都会，关键是能不能主动想到贪心、分治、双堆这类更优方案；第三是业务敏感度，题目会穿上自动驾驶的外衣，比如车辆调度、GPS轨迹、传感器数据流，如果完全不了解场景，很容易被题干绕进去。

还有一个隐藏前提容易被忽略：笔试时间通常只有 90 到 120 分钟，题量大约 3 到 4 道，这意味着每道题留给你从读题到调通的时间只有 30 分钟左右。想在这么短的时间内写出无 bug 的高质量代码，光靠临场发挥是不够的，必须提前把常见模型练成条件反射。所以我复盘这套题的目的很简单：让你看清题目背后的本质考点，下次遇到类似的场景化包装，能一眼识别出它到底在考什么。

1.2 这组真题涵盖的算法点

这套真题（二）里的三道题，恰好覆盖了三个不同方向的经典问题：

这三类问题在校招面试中出现频率极高，而且都有很强的扩展性。比如车辆调度本质上就是区间重叠问题，轨迹压缩就是经典的道格拉斯-普克算法，数据流中位数则是堆结构的典型应用。下面我按顺序逐题拆解。

2. 真题一：自动驾驶测试车辆调度（最小车辆数）

2.1 题目还原与问题转化

先还原一下题目大意：某自动驾驶测试场需要执行 n 个路测任务，每个任务有一个开始时间 start 和一个结束时间 end，一辆测试车同一时刻只能执行一个任务，问最少需要多少辆测试车才能完成所有任务。输入是一堆时间区间，输出是一个整数。

这道题的场景外衣很容易让人想到复杂的“车辆调度系统”，但其实把它剥开，就是一个很纯粹的区间问题：给定 n 个左闭右开区间 [start, end)，求同一时刻最多有多少个区间重叠。为什么呢？因为每个重叠的区间都需要一辆单独的车来执行，重叠数的最大值就是车辆数的下界；而只要车辆数足够覆盖最大重叠数，通过适当的任务分配一定可以排得开，所以最少车辆数就等于最大重叠数。

这里有个小细节：题目里的区间开闭会影响代码判断。我建议统一按左闭右开处理，即任务在 end 时刻已经结束、车辆可用。这样一辆车在 t 时刻空出来，另一个同样从 t 开始的任务就可以接上，符合实际场景。如果你习惯闭区间，代码里的判断条件要相应调整，面试时主动和面试官确认这一点会加分。

2.2 贪心加最小堆：从会议安排到车辆调度

最直接的做法是贪心加分堆。先把所有任务按开始时间从小到大排序，然后维护一个小顶堆来记录当前正在使用的每辆车的最早空闲时间。遍历每个任务时，先看堆顶那辆车的空闲时间：如果堆顶时间小于等于当前任务的开始时间，说明这辆车已经空出来了，直接弹出；然后把当前任务的结束时间放入堆中，代表这辆车在结束时间之前被占用。遍历结束后，堆的大小就是最少需要的车辆数。

int minVehicles(vector<pair<int, int>>& tasks) { sort(tasks.begin(), tasks.end()); // 按开始时间排序 priority_queue<int, vector<int>, greater<int>> 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(vector<pair<int, int>>& tasks, int maxTime) { vector<int> 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 vector<Point>& pts, int l, int r, double eps, vector<bool>& 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_queue<int> maxHeap; // 较小的一半，堆顶是较大的一半里最大的 priority_queue<int, vector<int>, greater<int>> 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，多问问自己“这个算法的前提假设是什么，什么场景下不适用”，这一层功夫到了，面场上你会有种“这题我见过”的踏实感。