Katkat
Back

Can All Courses Be Completed?

J.P. MorganSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to detect cycles in a directed graph to determine if a set of dependent tasks can be successfully completed.

Problem Statement

You are given an integer n representing the total number of courses, labeled from 0 to n - 1. You are also given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before you can take course a.

Return true if it is possible to finish all courses; otherwise, return false.

Function Signature

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

Constraints

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

Examples

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

Example 2: Input: n = 2, prerequisites = [[1, 0], [0, 1]] Output: false Explanation: This creates a cycle (0 -> 1 -> 0), so it is impossible to finish.

Edge Cases

  • A graph with no prerequisites.
  • A disconnected graph where multiple separate components exist.
  • A graph with 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

The problem is equivalent to detecting if a directed graph contains a cycle.

Hint 3

Consider using Kahn's Algorithm (topological sort using in-degrees) or Depth First Search with recursion stack tracking.

Follow-up questions

  • How would you modify your solution to return the actual order of courses if it is possible to finish them?
  • What is the time and space complexity of your solution in terms of V (vertices) and E (edges)?
  • How would you handle the case where there are multiple valid topological orders for a given set of prerequisites?