IntermediateGraphs
Course Schedule
Problem
There are numCourses courses labelled 0 … numCourses - 1. You are given a list prerequisites where [a, b] means you must take course b before course a. Return true if it is possible to finish all courses, and false otherwise.
Constraints
- 1 ≤ numCourses ≤ 10^5
- 0 ≤ prerequisites.length ≤ 5·10^3
- all pairs [a, b] are distinct
Examples
in: numCourses = 2, prerequisites = [[1,0]]
out: true
Take 0 then 1.
in: numCourses = 2, prerequisites = [[1,0],[0,1]]
out: false
0 needs 1 and 1 needs 0 — a cycle.
What this tests
- Modelling a word problem as a directed graph
- Realising "can finish all" means "the graph is acyclic"
- Kahn's algorithm (in-degree BFS) or DFS with three colours
- Handling disconnected components and isolated courses
- Distinguishing directed cycle detection from undirected
Pattern RecognitionSystematic ReasoningImplementationEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Return a valid order of courses (Course Schedule II).
F2
Return the courses that form a cycle, not just whether one exists.
F3
Each semester you can take any number of courses whose prerequisites are done. What is the minimum number of semesters?
F4
Each course has a duration, and you can take courses in parallel. What is the earliest finish time?