Question:
You are walking on a 2D map contoured with various heights of land that accumulates water when it rains. Specifically, when the rainwater height at any cell you are on is greater than or equal to the land height, that cell is submerged, i.e. you cannot walk to it.
What is the minimum water height that disconnects all paths between the top-left (start) and bottom-right (end) corners of this map?
You can only move in right angles, not diagonally (i.e. left, right, up, or down). Start (S) and End (E) are of infinite heights, i.e. they will never be submerged.
Given a large rectangular 2D grid of arbitrarily placed 1’s and 0’s, write a service that answers the query: How many 1's are in a given subgrid?
You should assume that the grid is large, doesn’t change, and is given to you ahead of time. The query will be called many times, so it needs to be fast.
这道题实际上混合了两个常见的面试场景：第一个是“随着水位上升，判断从左上角到右下角何时被阻断”，本质可以转化为图上的最小瓶颈路径 / 最短路问题，常见做法是用优先队列做类似 Dijkstra 的搜索，或者二分水位后用 BFS/DFS 检查连通性；第二个是“静态二维 0/1 矩阵多次查询子矩形 1 的个数”，典型解法是预处理二维前缀和，这样每次查询都能在 O(1) 时间返回答案。面试时重点是把题意还原成“可通行条件 + 多次快速查询”的数据结构设计问题。
