Course Schedule I
Microsoft
VisaThe problem
There are a total of N tasks, labeled from 0 to N-1. Given an array arr where arr[i] = [a, b] indicates that you must take course b first if you want to take course a. Find if it is possible to finish all tasks.
Input: N = 4, arr = [[1,0],[2,1],[3,2]]
Output: True
Explanation: It is possible to finish all the tasks in the order : 0 1 2 3. First, we will finish task 0. Then we will finish task 1, task 2, and task 3.
Input: N = 4, arr = [[0,1],[3,2],[1,3],[3,0]]
Output: False
Explanation: It is impossible to finish all the tasks. Let’s analyze the pairs: For pair {0, 1} -> we need to finish task 1 first and then task 0. (order : 1 0). For pair{3, 2} -> we need to finish task 2 first and then task 3. (order: 2 3). For pair {1, 3} -> we need to finish task 3 first and then task 1. (order: 3 1). But for pair {3, 0} -> we need to finish task 0 first and then task 3 but task 0 requires task 1 and task 1 requires task 3. So, it is not possible to finish all the tasks.
Input: N = 2, arr = [[1,0]]
- 1 <= N <= 2000
- 0 <= arr.length <= 5000
- arr[i].length == 2
- 0 <= arr[i][0], arr[i][1] < N
- All the pairs arr[i] are unique.
cpp
class Solution{
public:
bool canFinish(int N, vector<vector<int>> arr) {
}
};java
class Solution {
public boolean canFinish(int N, int[][] arr) {
}
}python
class Solution:
def canFinish(self, N, arr):javascript
class Solution {
canFinish(N, arr) {
}
}csharp
public class Solution
{
public bool canFinish(int N, List<int[]> arr)
{
}
}go
func canFinish(N int, arr [][]int) bool {
}Stuck? Show a way to structure it+
- 01Choose edge direction and explain it
- 02Build adjacency lists and indegree counts
- 03Queue all zero-indegree courses and peel edges
- 04Compare processed count with number of courses
Reference answer
Then expect these follow-ups
How would you return an ordering?
Tests: implementation extension
How can DFS detect the same cycle?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question