Katkat
Back

Determine Whether All Courses Can Be Completed

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model dependencies using a directed graph and detect cycles to determine if a set of tasks can be completed.

Determine Course Completion

There are a total of numCourses courses you need to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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

Function Signature

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= len(prerequisites) <= 5000
  • The input prerequisites may contain duplicate pairs.

Examples

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

Example 2: Input: numCourses = 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 cycle, so it is impossible.

Edge Cases

  • A graph with no prerequisites.
  • A graph with disconnected components.
  • A graph containing a self-loop (e.g., [1, 1]).

Hints

Hint 1

Represent the courses as nodes in a directed graph where an edge from u to v means u depends on v.

Hint 2

A set of courses can be completed if and only if the directed graph is a Directed Acyclic Graph (DAG).

Hint 3

Consider using Kahn's algorithm (BFS with in-degrees) or DFS with recursion stack tracking to detect cycles.

Follow-up questions

  • How would you return the actual order of courses if it is possible to complete them?
  • If the order is not possible, can you modify your algorithm to output the specific cycle that prevents completion?
  • How would the space and time complexity change if you used an adjacency matrix instead of an adjacency list?