InterviewCrunch

Beta

Course Schedule

Medium

Question

You're given a total number of courses to take and a 2D list that represents the prerequisites required for each course.

For example, [(4, 1), (2, 3)] means that you need to take course 4 BEFORE you can take course 1, and that you need to take course 2 BEFORE you can take course 3.

Return the ordered class schedule you can follow to finish all courses. If it's impossible to finish all courses, return an empty list.

Input: total = 2, prereqs = [(0, 1)]

Output: [0, 1]

You must take course 0 first before taking course 1. The solution is take course 0, then course 1.

Input: total = 2, prereqs = [(0, 1), (1, 0)]

Output: []

In this case, the 2 courses are prerequisites of each other, thus the scenario is impossible.

Input: total = 5, prereqs = [(0, 2), (1, 2), (2, 4), (3, 4)]

Output: [0, 1, 3, 2, 4]

The output follows the prerequisite ordering provided.

Note that other variations would be accepted as answers too:

  • [1, 0, 3, 2, 4]
  • [1, 3, 0, 2, 4]
  • [0, 3, 1, 2, 4]

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

What course schedule should the the following input return? total = 3, prereqs = [(0, 1), (1, 2), (2, 0)]
[]
[0, 1, 2]
[2, 1, 0]
[2, 0, 1]

Login or signup to save your code.

Notes

PrevPacific Atlantic Water Flow
NextCoding Pattern: Backtracking