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.
This prompt combines two classic interview patterns: a rising-water grid problem that asks for the minimum water level to block all paths from the top-left to the bottom-right, and a static 2D binary-matrix service that must answer repeated subgrid-count queries quickly. The first is typically solved with a shortest-path or minimum-bottleneck style search, while the second is best handled with a 2D prefix sum so each query can be answered in O(1).
