PPractick

The problem

The course planner now has to print an actual order in which to take all numCourses courses, given prerequisite pairs [a, b] (b before a), or return an empty list if it's impossible. That's a topological sort of the graph with edges b → a. Kahn's algorithm builds the order directly: repeatedly take a course whose prerequisites are all done, and if some courses are never freed, a cycle makes the schedule impossible.

Example: 4, [[1,0],[2,0],[3,1],[3,2]] → [0, 1, 2, 3].

Function signature

vector<int> findOrder(int numCourses, const vector<vector<int>>& prerequisites);  // empty if impossible

Test cases

Input (numCourses, prerequisites)	Output (queue seeded in index order)	Explanation
(2, [[1,0]])	[0, 1]
(4, [[1,0],[2,0],[3,1],[3,2]])	[0, 1, 2, 3]	[0, 2, 1, 3] is also valid
(3, [[0,1],[0,2]])	[1, 2, 0]	0 needs both 1 and 2
(2, [[0,1],[1,0]])	[]	A cycle
(1, [])	[0]

(Confirm: [a, b] means b before a; any valid order is accepted, and the one shown uses a FIFO queue seeded in index order.)

How interviewers phrase it

• "Return the ordering of courses you should take to finish all courses; if impossible, return an empty array" (LeetCode 210).

Clarifying questions to ask

1. Any valid order acceptable? (Yes.)
2. What to return for an impossible schedule? (An empty array.)
3. Can courses be unconnected to the rest? (Yes: they can go anywhere.)

Follow-ups to expect

1. "How does this differ from Course Schedule I?"
2. "DFS alternative?"
3. "How do you get the lexicographically smallest order?"
4. "Parallel semesters?"
5. "Complexity?"

Related questions

• Topological sort or Kahn's algorithm Hard
• Alien Dictionary Hard
• Connected Components Medium
• Traversal Techniques Medium
• Number of provinces Medium
• Connected Components Problem in Matrix Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in