最近一场 Google 技术面试中出现了一道二维矩阵模拟题，题目本身不算特别复杂，但很考验候选人对 边界条件、递归搜索以及重复计算优化 的处理。

英文原题

Given a 2D height map, determine where a raindrop starting at each cell eventually ends by always flowing to the steepest lower neighboring cell, with outside the grid treated as height 0. Return a 2D array where each cell contains the final (row, col) destination, including an out-of-bound coordinate if the water exits the grid.

比较直接的做法，是从每个格子分别开始模拟雨滴运动。

但如果每个格子都重新走完整条路径，会产生大量重复计算。例如：

A → B → C → D
    E → C → D

如果已经知道 C 最终会到达 D，那么以后走到 C 的雨滴就没必要再重新计算后面的路径。

因此这道题比较自然的优化方向是：

DFS / Simulation + Memoization

计算一个格子的最终 destination 后缓存结果，其他路径遇到它时直接复用。

由于每次只能流向严格更低的位置，高度会持续下降，因此正常情况下不会形成环，这一点也能简化处理。

整体可以做到接近：

Time:  O(rows × cols)
Space: O(rows × cols)

追问的地方

这题代码量并不是最大的难点，真正容易出问题的是规则细节。

比如题目中的 steepest lower neighboring cell 到底如何定义。如果两个方向下降高度完全相同，应该选择哪一个？邻居是上下左右四个方向，还是包含 diagonal？

原题描述中如果没有明确给出 tie-breaking rule，面试时最好主动向 interviewer 确认，而不是自己偷偷假设。

另外还有一个比较容易漏掉的条件：

grid 外面的高度是 0。

因此处理边缘格子时，不能只检查矩阵内部邻居，还需要把越界位置一起纳入比较。最终答案甚至可能是：

(-1, 3)
(5, 2)

这样的合法越界坐标。

csoahelp 面试辅助

如果是在真实 Google 面试中遇到这类题，很多时候困难并不是完全不会做，而是需要在几十分钟内同时完成：

理解题意 → 澄清规则 → 设计方案 → 分析复杂度 → 写代码 → Debug → 应对 follow-up。

csoahelp 提供技术面试实时文本辅助，可以在面试过程中帮助快速整理题意、提供解题方向、发现边界情况以及辅助应对 interviewer 的追问。

同时也提供 Google / Meta / Amazon 等公司 Mock Interview，可以提前按照真实面试节奏练习这类题目。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~