Determine Whether Courses Can Be Completed
SnapchatMachine Learning Engineer · Technical Screen
Last updated
This question evaluates understanding of graph modeling, directed cycle detection, and dependency resolution in the context of course prerequisites. It is commonly asked in the coding & algorithms domain because it reveals a candidate's algorithmic problem-solving ability and practical application of graph algorithms (expected O(V+E) time), testing practical implementation skills rather than only conceptual theory.
You are given an integer numCourses, representing courses labeled from 0 to numCourses - 1, and a list prerequisites.
Each prerequisite is a pair [course, prerequisite], meaning you must finish prerequisite before taking course.
Return true if it is possible to finish all courses. Return false if the prerequisite relationships contain a cycle that makes completion impossible.
Example:
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: Take course 0 first, then course 1.
Example:
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: Course 0 requires course 1, and course 1 requires course 0, so there is a cycle.
Expected complexity: O(V + E) time, where V is the number of courses and E is the number of prerequisite pairs.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.