Course Schedule II

Course Schedule II

What is this problem about?

The Course Schedule II interview question is an extension of the first Course Schedule problem. Instead of just saying if it's possible to finish all courses, you must return the actual order in which the courses should be taken. If it is impossible to finish all courses due to a cycle, you return an empty array.

Why is this asked in interviews?

Companies like Uber, LinkedIn, and Palantir ask this Topological Sort coding problem to see if you can not only detect dependencies but also produce a valid linear ordering. It tests your ability to manage state (the resulting schedule) during a graph traversal. It’s a very common real-world problem used in package managers (like npm or pip) and build systems (like Make or Bazel).

Algorithmic pattern used

The problem uses Topological Sort.

• Kahn's Algorithm (BFS): As you remove nodes with in-degree 0, add them to a result list. The order in which nodes are added to the queue is a valid topological sort.
• DFS: Perform a post-order traversal. After visiting all neighbors of a node, push the node onto a stack. The reverse of the stack is the valid ordering.

Example explanation

Courses: 4, Prerequisites: [[1,0],[2,0],[3,1],[3,2]]

1. Relationships: 0 is required for 1 and 2. 1 and 2 are required for 3.
2. In-degree 0: Course 0. Add 0 to result.
3. Neighbors of 0 are 1 and 2. Their in-degrees become 0.
4. Add 1 and 2 to result.
5. Neighbor of 1 and 2 is 3. Its in-degree becomes 0.
6. Add 3 to result. Valid order: [0, 1, 2, 3] (or [0, 2, 1, 3]).

Common mistakes candidates make

• Incomplete Result: Returning a partial list when a cycle prevents all courses from being included. You must check if result.size() == numCourses.
• Wrong Order in DFS: Forgetting that in DFS, the nodes are collected in reverse order (bottom-up), so the final list must be reversed.
• Handling Multi-edges: Not properly handling cases where the same prerequisite might be listed twice.

Interview preparation tip

Topological sort is only possible if the graph is a DAG (Directed Acyclic Graph). If the interviewer asks for the "lexicographically smallest" order, you should use a Priority Queue instead of a regular Queue in Kahn's algorithm.