Day 41: Non-overlapping Intervals

Day 41 — Non-overlapping Intervals

Coding problem

Solution outline (coding)

• Sort by end time (interval scheduling greedy).
• Greedily keep intervals that do not overlap with the last kept interval.
• Min removals = n - max non-overlapping.

Time complexity: O(n log n).

Space complexity: O(1) beyond sort.

from typing import List


class Solution:
  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    end = float('-inf')
    keep = 0
    for s, e in intervals:
      if s >= end:
        keep += 1
        end = e
    return len(intervals) - keep


# Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
# Output: 1

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).
campaigns(campaign_id, start_date, end_date). BigQuery: choose maximal non-overlapping campaign subset per region based on priority.

Tables implied by the prompt:

• campaigns(campaign_id, start_date, end_date)

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 Greedy to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ranked AS (
  SELECT campaign_id, start_date, end_date, priority,
    ROW_NUMBER() OVER (PARTITION BY region ORDER BY priority DESC, end_date) AS rn
  FROM campaigns
)
SELECT * FROM ranked WHERE rn <= 10;