Day 39: Meeting Rooms II

Day 39 — Meeting Rooms II

Coding problem

Solution outline (coding)

• Sort meetings by start time.
• Use a min-heap of end times: for each meeting, pop rooms freed before start; push new end.
• Heap size = rooms needed.

Time complexity: O(n log n).

Space complexity: O(n) — heap.

import heapq
from typing import List


class Solution:
  def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    if not intervals:
      return 0
    intervals.sort(key=lambda x: x[0])
    heap = []
    for s, e in intervals:
      if heap and heap[0] <= s:
        heapq.heapreplace(heap, e)
      else:
        heapq.heappush(heap, e)
    return len(heap)


# Input:  intervals = [[0,30],[5,10],[15,20]]
# Output: 2

SQL interview practice

1. Interview question

Companies / track: Google, Meta

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google, Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
same meetings table. BigQuery: compute minimal number of rooms required to host all meetings in a day (max concurrent meetings).

Tables implied by the prompt:

• day(max concurrent meetings)

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 Heap / Sort 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 points AS (
  SELECT room_id, start_ts AS t, 1 AS delta FROM meetings
  UNION ALL
  SELECT room_id, end_ts AS t, -1 AS delta FROM meetings
),
sweep AS (
  SELECT room_id, t, SUM(delta) OVER (PARTITION BY room_id ORDER BY t) AS concurrent
  FROM points
)
SELECT room_id, MAX(concurrent) AS min_rooms_needed FROM sweep GROUP BY room_id;