Databricks OA 面试复盘｜Matrix 跨列路径，最小极差如何找

Databricks 这道历史 OA 题允许从当前列跳到下一列的任意一行，路径代价是选中数字的最大值减最小值。难点在于：走到同一个格子，之前选过哪些数仍会影响最终答案。 2023 年 10 月的题目记录只给出这一道矩阵题，未标注地区。下面聚焦这道题；文中的矩阵是自拟演示例子。

第一题：每列选一个数，让极差最小

题目描述

给定 N 行 M 列的矩阵，从第一列任选起点，每次进入下一列的任意一行，直到最后一列。路径代价为所有选中值的最大值减最小值，求最小代价。N、M 都不超过 500，元素为不超过 10 亿的正整数。例如矩阵两行为 [1, 8, 7] 和 [6, 12, 10] 。逐列选最小值会得到 1、8、7，代价为 7；选择 6、8、7，代价只有 2，这才是最优路径。

解题思路

任意跨行都合法，问题可以直接改写为：找到一个最窄的数值区间，让每一列都至少有一个数落在区间里。把所有元素存成 (数值, 列号) 并按数值排序，随后维护滑动窗口。右端加入元素时增加该列计数；计数从 0 变为 1，已覆盖列数加一。窗口覆盖全部 M 列后，记录两端数值之差，再持续右移左端。删除某列的最后一个元素才会失去覆盖，窗口里有多个同列元素并不等于覆盖了多列。每一组合法选择都落在一个覆盖全部列的区间里，反过来也能从这样的区间为每列取一个值。两种表示互相对应，因此只需比较有效窗口的宽度。设元素总数 K=NM，排序和扫描共 O(K log K) 时间，额外空间 O(K+M)。需要返回具体路径时，保留最佳窗口，再为每列取其中一个元素。原题只要求代价；恢复路径可以作为练习追问。

Databricks OA 练习重点

先写出“每次能跳到下一列任意行”这条条件，再决定是否使用路径 DP。自测时加入单列、每列都有同一个值、重复值集中在一列，以及最优区间落在排序数组中间的情况。单列答案应为 0。申请流程要按地区和岗位核对。Abir Roy 的印度校招经历是 90 分钟四道 CodeSignal 题；另一个美国实习记录则是 CodeSignal 后接招聘沟通、两轮技术面和行为面。两者都不能用于推断这道历史矩阵题的题号或当前测评时长。

FAQ

为什么不能用普通最短路径算法？

代价不是边权之和。仅记录到达某格子的最小极差，会丢掉当前最小值和最大值，后续加入同一个数时，两条路径的变化不同。

窗口里出现重复值如何处理？

按列计数，保留重复元素。只有某列计数从 1 减到 0 时，窗口才不再覆盖这一列。

能否用堆降低额外空间？

可以优先把每列排序，再用最小堆各放一个候选值，并维护当前最大值。每次推进最小值所属的列；某列耗尽时停止。堆本身占 O(M) 空间，排序所需空间另计。

参考来源

2023年矩阵跨列题候选人原帖 Abir Roy 印度校招实习申请经历美国实习候选人的 CodeSignal 后续流程

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

微信：Coding0201
邮箱：[email protected]
Telegram：@OAVOProxy
WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。