Quick Overview

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.

Determine Whether Courses Can Be Completed

Company: Snapchat

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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: ```text Input: numCourses = 2, prerequisites = [[1, 0]] Output: true Explanation: Take course 0 first, then course 1. ``` Example: ```text 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.

Overview: 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.

Read the full Snapchat Machine Learning Engineer interview experience this question came from

You are given an integer numCourses representing courses labeled from 0 to numCourses - 1, and a list prerequisites. Each prerequisite pair [course, prerequisite] means you must complete prerequisite before taking course. Return True if it is possible to finish all courses, and False if the prerequisite relationships contain a cycle that makes completing every course impossible.

Constraints

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

Examples

Input: (2, [[1, 0]])

Expected Output: True

Explanation: Course 0 has no prerequisite, so you can take 0 first and then 1.

Input: (2, [[1, 0], [0, 1]])

Expected Output: False

Explanation: Course 0 depends on 1 and course 1 depends on 0, forming a cycle.

Hints

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

Loading coding console...