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
Coding & Algorithms
Software Engineer
ByteDance
March 3, 2025
Software Engineer
Coding Round
Coding & Algorithms
Medium

15

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
Topological sort
BFS
Cycle detection
Directed graphs
Course scheduling
How to Approach This
  1. Clarify input constraints and edge cases before writing code.
  2. Walk through your approach verbally and confirm with the interviewer before coding.
  3. Start with a brute force solution, then optimize. Mention time and space complexity.
  4. Test your solution with examples, including edge cases like empty input or duplicates.
  5. 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 Problems
Sample 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
Markdown supported

Related Questions