Produce a Deterministic Course Plan
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Produce a Deterministic Course Plan
There are num_courses courses numbered 0 through num_courses - 1. Each prerequisite pair is [course, prerequisite], meaning prerequisite must appear before course.
~~~python
def prerequisite_plan(
num_courses: int,
prerequisites: list[list[int]]
) -> list[object]:
...
~~~
Return [true, order] if every course can be completed, where order is the lexicographically smallest valid list of all course IDs. Return [false, []] if the requirements contain a cycle. Duplicate prerequisite pairs do not change the result.
## Constraints and Boundary Rules
- 0 <= num_courses <= 200000
- 0 <= len(prerequisites) <= 400000
- Every pair must contain exactly two integer IDs in range.
- Self-dependencies are cycles.
- For num_courses == 0, return [true, []].
- Malformed pairs or out-of-range IDs must raise ValueError.
- Inputs and outputs are JSON-marshalable and outputs are compared exactly.
## Examples
~~~text
Input: num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [true, [0, 1, 2, 3]]
Input: num_courses = 2
prerequisites = [[1, 0], [0, 1]]
Output: [false, []]
Input: num_courses = 3
prerequisites = []
Output: [true, [0, 1, 2]]
~~~
## Hints
- Model what makes a course eligible at any moment.
- The ordinary valid-order problem does not choose between simultaneous options; the requested output does.
- Ensure duplicate edges do not distort eligibility.
Quick Answer: Return the lexicographically smallest valid course order from prerequisite pairs, or report a cycle. Handle duplicate edges, malformed IDs, self-dependencies, empty course sets, and large graphs with deterministic topological sorting.
Return whether all numbered courses can be completed and, when possible, the lexicographically smallest full topological order. A pair [course, prerequisite] requires the prerequisite first; duplicate pairs do not change indegrees.
Constraints
- Courses are numbered 0 through num_courses - 1.
- There may be 200,000 courses and 400,000 pairs.
- Self-dependencies and longer cycles are impossible to schedule.
- Malformed or out-of-range pairs raise ValueError.
Examples
Input: {'num_courses':4,'prerequisites':[[1,0],[2,0],[3,1],[3,2]]}
Expected Output: [True, [0, 1, 2, 3]]
Explanation: The supplied DAG has a deterministic smallest order.
Input: {'num_courses':2,'prerequisites':[[1,0],[0,1]]}
Expected Output: [False, []]
Explanation: A directed cycle blocks completion.
Hints
- Use Kahn's topological algorithm.
- A min-heap chooses the smallest currently eligible course.
- Deduplicate edges before changing indegrees.