Day 65: Trapping Rain Water

Day 65 — Trapping Rain Water

Coding problem

Solution outline (coding)

• Two pointers: left/right with left_max and right_max water levels.
• Add trapped water when the smaller side is binding; move that pointer.
• Alternative: monotonic stack for bars.

Time complexity: O(n).

Space complexity: O(1) two-pointer; O(n) stack variant.

from typing import List


class Solution:
  def trap(self, height: List[int]) -> int:
    if not height:
      return 0
    lo, hi = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while lo < hi:
      if height[lo] < height[hi]:
        left_max = max(left_max, height[lo])
        water += left_max - height[lo]
        lo += 1
      else:
        right_max = max(right_max, height[hi])
        water += right_max - height[hi]
        hi -= 1
    return water


# Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
rainfall(grid_id, pos, height). BigQuery: approximate trapped water via pre-aggregated local minima/maxima; discuss tradeoffs vs exact algorithms in code.

Tables implied by the prompt:

• rainfall(grid_id, pos, height)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map Two Ptrs / Stack to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Aggregate: fix GROUP BY keys, then HAVING for thresholds (e.g. min volume).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT grid_id, SUM(local_min) AS approx_trap FROM rainfall_agg GROUP BY grid_id;