Course Schedule II with Topological Sort
Last updated: March 3, 2025
Quick Overview
Given a list of course prerequisites represented as pairs of courses, determine if it's possible to finish all courses and return the order in which to take them using topological sort. If it is impossible to complete all courses due to cyclic dependencies, return an empty list. The input consists of an integer `numCourses` and a list of prerequisite pairs, and the output should be a list of course indices in the order they should be taken.
ByteDance
March 3, 202515
4
2,010 solved
Given a list of course prerequisites represented as pairs of courses, determine if it's possible to finish all courses and return the order in which to take them using topological sort. If it is impossible to complete all courses due to cyclic dependencies, return an empty list. The input consists of an integer `numCourses` and a list of prerequisite pairs, and the output should be a list of course indices in the order they should be taken.
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
Problem Analysis
In this problem, we need to determine if we can complete all courses given their prerequisite pairs. This can be interpreted as a directed graph where each course is a node and each prerequisite relat...
Approach
- Graph Representation: We will represent the courses and their prerequisites using an adjacency list, where each course points to its dependent courses. Additionally, we will maintain an array t...
Submit Your Answer
