Given an elevation map, compute how much water it can trap after raining.
Whether you can find the local rule, that water above a column is decided by the tallest bar on each side, before optimising.
CodingHard
Who reports being asked this
Adobe · Amazon · Bloomberg · Goldman Sachs
What a strong answer does
Start by saying the local rule before discussing pointers or cleverness. For any column i, the water sitting above it is determined by the shorter of the tallest wall to its left and the tallest wall to its right. In formula terms, water_i = min(left_max_i, right_max_i) - height[i], floored at zero. If either side is not tall enough, water spills away on that side. This rule is the whole problem; every implementation is just a different way to compute those two maxima for every position.