Katkat
Back

Course Schedule Feasibility

ByteDanceSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to detect cycles in a directed graph using topological sorting or Depth First Search, ensuring all task dependencies can be resolved.

Problem Statement

You are given an integer n representing the total number of courses, labeled from 0 to n-1. Some courses have prerequisites, where the prerequisite [a, b] means you must take course b before course a.

Given the total number of courses and a list of prerequisite pairs, determine if it is possible to finish all courses. Return true if it is possible, and false otherwise.

Function Signature

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:

Constraints

  • 1 <= num_courses <= 2000
  • 0 <= len(prerequisites) <= 5000
  • All pairs in prerequisites are unique.

Examples

Example 1: Input: num_courses = 2, prerequisites = [[1, 0]] Output: true Explanation: There are 2 courses. To take course 1, you must take course 0. Both can be completed.

Example 2: Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]] Output: false Explanation: To take course 1 you need 0, and to take 0 you need 1. This creates a circular dependency.

Edge Cases

  • A graph with no prerequisites (should return true).
  • A graph with disconnected components.
  • A self-loop (e.g., [0, 0]).

Hints

Hint 1

Represent the courses as nodes in a directed graph and the prerequisites as directed edges.

Hint 2

A schedule is impossible if and only if there is a cycle in the directed graph.

Hint 3

You can use Kahn's algorithm (topological sort via in-degrees) or DFS with a recursion stack to detect cycles.

Follow-up questions

  • How would you modify your solution to return the actual order of courses if it is possible to complete them?
  • What is the time and space complexity of your solution in terms of V (courses) and E (prerequisites)?
  • How would your approach change if the prerequisites had associated weights representing the time taken to complete each course?