Course Schedule
Medium About 20 min Free, no account needed
Can every course be finished, or do the prerequisites form a cycle?
The brief
There are numCourses courses; prerequisites[i] = [a, b] means course b
must be taken before course a. Return true when every course can be
finished, i.e. the prerequisite graph has no cycle.
The obvious approach walks the dependency chain from every course by rescanning the whole edge list at every step, O(V * E * depth). The hidden test is a 2,000-course chain, which times it out. You need to detect a cycle without rescanning the edge list at every step; an O(V + E) solution clears the bar.
Starter code
using System;
public class Solution
{
// TODO: return true when the prerequisite graph has no cycle.
public bool CanFinish(int numCourses, int[][] prerequisites)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Topological sort
- Order a dependency graph and detect when its prerequisites form a cycle.
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.