Katkat
Back

Find a Valid Course Order

AmazonSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to detect cycles in a directed graph and perform a topological sort to resolve dependencies.

Problem: Course Schedule Order

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses have prerequisites, expressed as a list of pairs where [a, b] means you must take course b before course a.

Given the total number of courses n and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. If there are multiple valid orderings, return any of them. If it is impossible to finish all courses (i.e., there is a cyclic dependency), return an empty list.

Function Signature

def find_course_order(n: int, prerequisites: List[List[int]]) -> List[int]:

Constraints

  • 1 <= n <= 2000
  • 0 <= len(prerequisites) <= n * (n - 1) / 2
  • All prerequisite pairs are unique.

Examples

Example 1: Input: n = 2, prerequisites = [[1, 0]] Output: [0, 1] Explanation: Course 0 must be taken before course 1.

Example 2: Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: [0, 1, 2, 3] or [0, 2, 1, 3] Explanation: Course 0 is a prerequisite for 1 and 2, which are both prerequisites for 3.

Example 3: Input: n = 2, prerequisites = [[1, 0], [0, 1]] Output: [] Explanation: There is a cycle (0 -> 1 -> 0), so no valid order exists.

Edge Cases

  • n with no prerequisites.
  • Disconnected components in the graph.
  • Graphs with direct or indirect cycles.

Hints

Hint 1

Represent the courses as nodes in a directed graph where an edge from `b` to `a` means `b` is a prerequisite for `a`.

Hint 2

Consider using Kahn's algorithm, which relies on tracking the 'in-degree' (number of incoming edges) of each node.

Hint 3

If you finish processing all nodes and the result list contains fewer than `n` nodes, a cycle exists.

Follow-up questions

  • How would you modify your solution if the input was a dictionary mapping courses to a list of their prerequisites?
  • What is the time and space complexity of your solution in terms of courses `V` and prerequisite pairs `E`?
  • How would you handle a scenario where you need to report the exact minimum number of semesters required to finish all courses, assuming you can take an unlimited number of courses simultaneously?