Day 32: Course Schedule II

Day 32 — Course Schedule II

Coding problem

Solution outline (coding)

• Same topo as Course Schedule I, but output the full order array when acyclic.
• If cycle detected, return empty array.
• Use Kahn or DFS post-order reversed.

Time complexity: O(V + E).

Space complexity: O(V + E).

from typing import List
from collections import deque


class Solution:
  def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    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])
    order = []
    while q:
      u = q.popleft()
      order.append(u)
      for v in g[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
          q.append(v)
    return order if len(order) == numCourses else []


# Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
# Output: [0,1,2,3] (one valid order)

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).
Same schema. BigQuery: compute a valid topological ordering (course plan) with level numbers (semester index).

Tables implied by the prompt:

• ordering(course plan)
• numbers(semester index)

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).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH RECURSIVE ord AS (
  SELECT course_id, 0 AS semester FROM courses WHERE course_id NOT IN (SELECT course_id FROM prereq)
  UNION ALL
  SELECT p.course_id, o.semester + 1
  FROM prereq AS p
  JOIN ord AS o ON p.prereq_id = o.course_id
)
SELECT course_id, MIN(semester) AS plan_order FROM ord GROUP BY course_id ORDER BY plan_order;