Databricks 的技术积累深厚，面试官的经验往往也十分扎实，能够很快判断候选人对于算法、数据结构和工程实现的掌握程度。整个phone screen持续六十分钟，通常包括开场几分钟的寒暄，随后五十分钟的解题环节，其中包含一个主问题和一个 follow-up，最后五分钟留给候选人与面试官的自由问答。因为题目的难度偏中等偏上，而时间并不宽裕，所以写出的代码必须能够正确运行，并且通过面试官提供的测试用例和自己设计的额外测试用例，这对代码的完整性和正确性都有较高要求。

我遇到的是一道老题目，网上有原题，关于通勤的线路。题目的背景是一个城市街区的二维网格，每个格子可能代表一种交通方式、路障 block、起点 S 或终点 D。候选人需要从起点走到终点，但只能选择一种交通方式并且全程只能在该方式对应的格子中移动（上下左右），终点 D 是唯一的例外，允许在任何情况下进入。整个路径的时间定义为路径长度乘以该交通方式的单位时间，而成本是路径长度乘以该交通方式的单位成本。任务要求找出能够让 S 到 D 的总时间最小的交通方式，如果存在并列情况则再比较总成本，若没有任何方式能够到达 D，则返回 None。

解题思路是先扫描整个网格，定位出起点和终点的坐标。然后针对每一种交通方式进行一次广度优先搜索 BFS，从起点开始只在该方式的格子中扩展，直到能够进入终点。由于 BFS 保证第一次到达终点的路径即为最短路径，因此可以直接得到路径长度，再结合该方式的单位时间和单位成本计算出总时间与总成本。在所有交通方式的结果中，首先比较最小的总时间，如果出现并列再比较总成本，最终得到最佳的方案。如果所有 BFS 都无法抵达终点，则结果为 None。整个算法的复杂度是 O(t × R × C)，其中 t 是交通方式的总数，R 和 C 分别是网格的行数和列数。

在 follow-up 中，问题变得更复杂，因为允许路径中混合使用不同的交通方式，只要相邻的格子不是路障，就可以在移动时切换到新的方式。这样一来，问题不再适合用单一 BFS 来解决，而需要转化为一个加权最短路问题。此时网格中的每一个格子都可以看作图中的节点，边的权重取决于进入格子时所选择交通方式的单位时间。候选人需要在整个网格上运行 Dijkstra 算法，不断扩展累计时间，直到到达终点。Dijkstra 保证能够找到全局最优的最短时间路径，并自然考虑了所有可能的交通方式切换。

砖厂的大部分coding都是老题，地里都能翻到原题。但是难度确实不小。