Interview Question Bank · WITH RECURSIVE · shortest depth · dedupe
12. Every prerequisite of the capstone
HardEducationQuestion #228
Concept: WITH RECURSIVE · shortest depth · dedupeshow
A recursive CTE walks a hierarchy one level at a time: the anchor query picks the starting rows, and the recursive part joins the CTE back to the edge table to find the next level, repeating until no new rows appear. Carry a depth counter (depth + 1) as you go. When a node can be reached by more than one path it shows up once per path, so GROUP BY the node and take MIN(depth) for the shortest route.
Example (different data):
WITH RECURSIVE up AS ( SELECT manager_id AS id, 1 AS levels FROM staff WHERE id = 42 UNION ALL SELECT s.manager_id, up.levels + 1 FROM up JOIN staff s ON s.id = up.id WHERE s.manager_id IS NOT NULL ) SELECT id, levels FROM up;
Your task
Brightpath Academy's advisors want one checklist for the Capstone Project (course id 8): every course a student must pass first, including prerequisites of prerequisites.
Return course (title) and steps_away (1 for a direct prerequisite of the Capstone Project, 2 for a prerequisite of one of those, and so on, using the shortest path when a course is reachable several ways) for every course the capstone depends on, each listed once. Sort by steps_away, then course.
Starting Postgres in your browser…
Checking your access…