Coding

Course Schedule I

Asked at

Microsoft

Visa

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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)
    {
     
    }
}

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

Start by restating the input contract for Course Schedule I and testing the smallest boundary case before choosing the algorithm. Treat each prerequisite pair as a directed edge prerequisite -> course. Kahn's topological sort repeatedly takes courses with indegree zero. If it processes all courses, no prerequisite cycle exists and finishing is possible. Explain the invariant while coding, then show how each update preserves it. Kahn's algorithm takes O(V + E) time and O(V + E) space for adjacency lists, indegrees, and the queue. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

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

Hiring now

Visa has 638 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer Intern
GB - London, United Kingdom
Sr. Software Engineer (3+ yrs, DevOps, Cloud, Coding, Infra)
IN - Bengaluru, India
Sr Software Engineer (3-5 yrs of exp - Full stack development, Java, React, Gen AI)
IN - Bengaluru, India

Or practice this question first

Next question