Order Classes by Prerequisites with Recursive DFS
Company: Vanta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Order Classes by Prerequisites with Recursive DFS
Implement `class_order(classes, prerequisites)` using recursive depth-first search.
`classes` contains distinct class names. Each item `[course, prerequisite]` in `prerequisites` means `prerequisite` must be completed before `course`. Return an ordering containing every class exactly once and satisfying every prerequisite.
The result must be deterministic: start DFS roots in the order given by `classes`, visit each course's prerequisites in the order their pairs appear in `prerequisites`, and append a course after all of its prerequisites. If the dependency graph contains a cycle, return `[]`.
## Function Contract
```python
def class_order(classes: list[str], prerequisites: list[list[str]]) -> list[str]:
...
```
## Examples
```text
classes = ["Compilers", "Algorithms", "AI", "Databases"]
prerequisites = [
["Compilers", "Algorithms"],
["AI", "Algorithms"],
]
result = ["Algorithms", "Compilers", "AI", "Databases"]
```
```text
classes = ["A", "B", "C"]
prerequisites = [["A", "B"], ["B", "C"], ["C", "A"]]
result = []
```
## Constraints
- `0 <= len(classes) <= 1_000`
- `0 <= len(prerequisites) <= 20_000`
- Every prerequisite pair contains two names from `classes`.
- There are no duplicate prerequisite pairs.
- The implementation must use recursive DFS, with enough states to distinguish an active recursion path from a completed node.
Overview: Build a deterministic prerequisite ordering with recursive depth-first search. Handle disconnected classes and detect dependency cycles by tracking both active and completed nodes.
Implement class_order(classes, prerequisites) using recursive depth-first search.
classes contains distinct class names. Each pair [course, prerequisite] means the prerequisite must be completed before the course. Return every class exactly once in a valid order. For deterministic output, start DFS roots in classes order, visit each course's prerequisites in pair-input order, and append a course after all its prerequisites. Return [] if a cycle exists.
Constraints
- 0 <= len(classes) <= 1,000
- 0 <= len(prerequisites) <= 20,000
- Class names are distinct strings and every pair references listed classes.
- There are no duplicate prerequisite pairs.
- The implementation uses recursive DFS with active and completed states.
Examples
Input: ([], [])
Expected Output: []
Explanation: The empty catalog has an empty valid order.
Input: (["A"], [])
Expected Output: ["A"]
Explanation: A lone class has no prerequisites.
Hints
- Build each course's prerequisite list without reordering the pairs.
- Three states—unvisited, active, and completed—distinguish a back edge from shared work.
- Append a course only after every prerequisite DFS returns successfully.