MediumGraphsAI interview only

Course Schedule

Asked atamazonmetamicrosoftgoogleapplebloomberg

01 · Problem

There are a total of numCourses courses you have 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.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

02 · Examples

Example 01

Input

numCourses = 2, prerequisites = [[1,0]]

Output

true

There are 2 courses. To take course 1, you must first finish course 0. This is achievable by taking course 0 first, then course 1.

Example 02

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

false

Course 1 requires course 0, and course 0 requires course 1. This creates a circular dependency (cycle), making it impossible to finish all courses.

Example 03

Input

numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]

Output

true

The courses form a linear dependency chain 0 → 1 → 2 → 3 with no cycles. Take them in order: 0, 1, 2, 3.

03 · Constraints

011 <= numCourses <= 2000
020 <= prerequisites.length <= 5000
03prerequisites[i].length == 2
040 <= ai, bi < numCourses
05All the pairs prerequisites[i] are unique.

04 · Optimal complexity

Time: O(V + E)
Space: O(V + E)

05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem