Katkat
Back

Course Prerequisite Feasibility

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to detect cycles in a directed graph to determine if a set of academic courses with prerequisite constraints can be completed.

Problem Statement

You are given an integer n representing the 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 (a prerequisite relationship).

Write a function canFinish(n, prerequisites) that returns true if it is possible to finish all courses, and false otherwise. If a cycle exists in the dependency graph, it is impossible to complete the courses.

Constraints

  • 1 <= n <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2

Examples

Example 1:

  • Input: n = 2, prerequisites = [[1, 0]]
  • Output: true
  • Explanation: To take course 1, you must take course 0. This is possible.

Example 2:

  • Input: n = 2, prerequisites = [[1, 0], [0, 1]]
  • Output: false
  • Explanation: Course 1 requires course 0, and course 0 requires course 1. This is a circular dependency.

Edge Cases

  • A graph with no prerequisites (always return true).
  • A graph that is disconnected (multiple separate components of courses).

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 the directed graph contains a cycle.

Hint 3

You can use Depth-First Search (DFS) with a state array (e.g., visiting vs. visited) or Kahn's algorithm for topological sorting to detect cycles.

Follow-up questions

  • If the courses can be finished, can you return the actual order in which to take them?
  • How would your approach change if the prerequisite graph was allowed to have duplicate dependencies or self-loops?
  • What is the time and space complexity of your solution in terms of `n` and the number of edges `E`?