Day 31: Course Schedule

Day 31 — Course Schedule

Coding problem

Solution outline (coding)

• Build adjacency list; compute in-degree per course.
• Kahn: repeatedly pick in-degree 0, append to order, relax edges; cycle if not all processed.
• Or DFS with three colors for cycle detection.

Time complexity: O(V + E).

Space complexity: O(V + E) — graph + queue/stack.

from typing import List
from collections import deque


class Solution:
  def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    g = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for a, b in prerequisites:
      g[b].append(a)
      indeg[a] += 1
    q = deque([i for i in range(numCourses) if indeg[i] == 0])
    taken = 0
    while q:
      u = q.popleft()
      taken += 1
      for v in g[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
          q.append(v)
    return taken == numCourses


# Input:  numCourses = 2, prerequisites = [[1,0]]
# Output: True

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).
courses(course_id), prereq(course_id, prereq_id). BigQuery: detect cycles and output one invalid course sequence using recursive CTE or iterative approach.

Tables implied by the prompt:

• courses(course_id)
• prereq(course_id, prereq_id)

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 Topological Sort to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH RECURSIVE topo AS (
  SELECT course_id, 0 AS lvl FROM courses WHERE course_id NOT IN (SELECT course_id FROM prereq)
  UNION ALL
  SELECT p.course_id, t.lvl + 1
  FROM prereq AS p
  JOIN topo AS t ON p.prereq_id = t.course_id
)
SELECT course_id, MAX(lvl) FROM topo GROUP BY course_id;