Day 10: Container With Most Water

Day 10 — Container With Most Water

Coding problem

Solution outline (coding)

• Place pointers at the leftmost and rightmost vertical lines.
• Compute area = width × min(height[left], height[right]); track the maximum.
• Move the pointer at the shorter line inward — keeping the taller side can only increase min height.

Time complexity: O(n) — each pointer moves at most n steps.

Space complexity: O(1).

from typing import List


class Solution:
  def maxArea(self, height: List[int]) -> int:
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
      best = max(best, min(height[lo], height[hi]) * (hi - lo))
      if height[lo] < height[hi]:
        lo += 1
      else:
        hi -= 1
    return best


# Input:  height = [1,8,6,2,5,4,8,3,7]
# Output: 49

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).
heights(sample_id, pos, height). BigQuery: sketch approach (arrays/UDF) to approximate max contained water per sample_id; explain why application code is preferable and how to minimize scan cost in SQL.

Tables implied by the prompt:

• heights(sample_id, pos, height)
• approach(arrays/UDF)

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 Pointers to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Cost: selective columns, partition pruning, avoid SELECT * when tables are huge.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH arr AS (
  SELECT sample_id, ARRAY_AGG(STRUCT(pos, height) ORDER BY pos) AS bars
  FROM heights
  GROUP BY sample_id
)
SELECT
  sample_id,
  ARRAY_LENGTH(bars) AS n,
  -- Exact max water belongs in application code; SQL holds ordered heights for export to a UDF.
  (SELECT STRING_AGG(CAST(height AS STRING), ',' ORDER BY pos) FROM UNNEST(bars)) AS heights_csv
FROM arr;