Katkat
Back

Determine if all courses can be completed

AmazonApplied Scientist · Technical Screen
MediumApplied ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model prerequisites as a directed graph and detect cycles to determine if a valid topological ordering exists.

Problem Statement

You are given n courses labeled from 0 to n-1. Some courses have prerequisites, represented by a list of pairs prerequisites, where prerequisites[i] = [a, b] indicates that you must take course b before you can take course a.

Given the total number of courses n and a list of prerequisites, 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: There is no cycle; you take course 0, then course 1.

Example 2: Input: n = 2, prerequisites = [[1, 0], [0, 1]] Output: false Explanation: A cycle exists (0 -> 1 -> 0), making it impossible to complete the courses.

Edge Cases

  • n = 1 (no prerequisites possible).
  • Disconnected components in the graph.
  • A prerequisite chain that covers all nodes vs. a partial chain.

Hints

Hint 1

Represent the courses as nodes in a directed graph where an edge from `b` to `a` means `b` is a prerequisite for `a`.

Hint 2

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

Hint 3

You can use Kahn's algorithm (Breadth-First Search for topological sort) by tracking the in-degree of each node or perform a Depth-First Search using a recursion stack to detect back-edges.

Follow-up questions

  • If it is possible to finish all courses, can you return the actual order of courses you should take?
  • What is the time and space complexity of your solution in terms of `n` and the number of edges `E`?
  • How would you modify your algorithm if some courses could be taken in parallel, provided their individual prerequisites are met?