Trapping Rain Water at Google — Interview Guide

• Water above a bar is bounded by the min of the tallest bars to its left and right.
• Two pointers exploit that the trapped water at each end depends only on the shorter boundary.
• A monotonic decreasing stack also solves it by matching basins.

def trap(h):
    l, r = 0, len(h) - 1
    left_max = right_max = water = 0
    while l < r:
        if h[l] < h[r]:
            left_max = max(left_max, h[l])
            water += left_max - h[l]
            l += 1
        else:
            right_max = max(right_max, h[r])
            water += right_max - h[r]
            r -= 1
    return water

• Algorithmic fluency — the right data structure and the optimal complexity, fast.
• Googleyness — comfort with ambiguity, intellectual curiosity, and a collaborative style.
• Leadership and impact — especially at L4+; evidence of driving outcomes.
• Communication — explaining your thinking as you solve.