Day 38: Merge Intervals

Day 38 — Merge Intervals

Coding problem

Solution outline (coding)

• Sort intervals by start (and end as tiebreaker).
• Merge: if current start ≤ previous end, extend previous end; else append new interval.
• Return merged list.

Time complexity: O(n log n) — dominated by sort.

Space complexity: O(n) — output (or O(1) if in-place allowed).

from typing import List


class Solution:
  def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    out = []
    for s, e in intervals:
      if not out or s > out[-1][1]:
        out.append([s, e])
      else:
        out[-1][1] = max(out[-1][1], e)
    return out


# Input:  intervals = [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]

SQL interview practice

1. Interview question

Companies / track: Meta, Google, Netflix

Cross-FAANG mix: combines ads-scale logs, product engagement, and subscription-style retention questions—expect heavy joins and time windows.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta, Google, Netflix**-scale surfaces (ads, product, or engagement — as the tables suggest).
meetings(room_id, start_ts, end_ts). BigQuery: merge overlapping intervals per room and compute total occupied time per day.

Tables implied by the prompt:

• meetings(room_id, start_ts, end_ts)

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 Sort + Sweep to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Filter time first: predicate on DATE(ts) / partition column before heavy joins; state the window in plain English.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ordered AS (
  SELECT room_id, start_ts, end_ts,
    MAX(end_ts) OVER (PARTITION BY room_id ORDER BY start_ts ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS prev_end
  FROM meetings
),
merged AS (
  SELECT room_id, start_ts, end_ts,
    SUM(CASE WHEN start_ts > prev_end THEN 1 ELSE 0 END) OVER (PARTITION BY room_id ORDER BY start_ts) AS grp
  FROM ordered
)
SELECT room_id, grp, MIN(start_ts) AS ms, MAX(end_ts) AS me,
  TIMESTAMP_DIFF(MAX(end_ts), MIN(start_ts), SECOND) AS occupied_sec
FROM merged
GROUP BY room_id, grp;