Course Schedule II with Topological Sort
Last updated: March 3, 2025
Quick Overview
Given course prerequisites, return the order to take all courses, or determine it's impossible. Tests graph traversal and cycle detection.
ByteDance
March 3, 202515
4
2,010 solved
Given course prerequisites, return the order to take all courses, or determine it's impossible. Tests graph traversal and cycle detection.
Graph BFS/DFS with topological sort is a top-3 pattern at ByteDance. This problem combines ordering and cycle detection.
What the Interviewer Expects
- Implement Kahn's algorithm (BFS-based topological sort)
- Detect cycles that make ordering impossible
- Handle disconnected components
- Return a valid ordering, not just feasibility
- Discuss time and space complexity
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you find all valid orderings?
- What if some courses can be taken in parallel?
- How would you handle weighted prerequisites?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Implementation
```python from collections import deque, defaultdict def find_order(num_courses, prerequisites): graph = defaultdict(list) in_degree = [0] * ...
Cycle Detection
If len(order) < num_courses after BFS completes, there must be a cycle (remaining nodes have non-zero in-degree that can never be reduced to zero). Re...
Submit Your Answer
