Coding questions · Snapchat

Determine Whether Courses Can Be Completed

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.

Determine Whether Courses Can Be Completed

Constraints

1 <= numCourses <= 100000
0 <= len(prerequisites) <= 200000
Each prerequisite is a pair [course, prerequisite] with 0 <= course, prerequisite < numCourses

Hints

Model the courses as a directed graph where prerequisite -> course is a directed edge.
If you repeatedly take courses with no remaining prerequisites and still cannot process all courses, then a cycle exists.