Cycle Detection Algorithm

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Cycle Detection Algorithm. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Implement an algorithm to detect if there are any cyclical dependencies in a list of course prerequisites.

Implement can_finish(num_courses, prerequisites), where prerequisites contains pairs [course, prerequisite], meaning the prerequisite must be completed first. Return True if every course can be completed, or False if any dependency cycle exists. Courses are numbered from 0 through num_courses - 1.

Constraints

1 <= num_courses <= 5000
0 <= prerequisites.length <= 10000
Each prerequisite pair has exactly two integers
0 <= course, prerequisite < num_courses
Duplicate prerequisite pairs may appear

Function Signature

def can_finish(num_courses, prerequisites):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output