Interview challenge · medium · graph, topological-sort, dfs, bfs
Course Schedule
The challenge
There are n courses, numbered from 0 to n - 1, and a list of prerequisite pairs [a, b]: you must take course b before course a. Return true if it is possible to finish every course. In graph terms: the prerequisites form a directed graph, and you can finish only if it has no cycle.
Example
n = 2, [[1, 0]] -> true (take 0, then 1)
n = 2, [[1, 0], [0, 1]] -> false (each waits for the other)
n = 4, [[1, 0], [2, 1], [3, 1]] -> true (0, 1, then 2 and 3)Idea: topological sort (Kahn's algorithm). Count how many prerequisites each course still waits on and start with the courses that wait on none. Every time you take a course, the courses it unlocks wait on one less; when one reaches zero, it is ready too. If you end up taking all n courses there is no cycle; if a cycle exists, its courses never reach zero and stay stuck. Time O(n + p), where p is the number of pairs.
The solution
# Course Schedule - ayotl.dev
def can_finish(n, pre):
# need[c] = prerequisites c waits on
need = [0] * n
unlocks = [[] for _ in range(n)]
for a, b in pre:
unlocks[b].append(a)
need[a] += 1
# take the free courses first
ready = [c for c in range(n)
if need[c] == 0]
done = 0
while ready:
c = ready.pop()
done += 1
for a in unlocks[c]:
need[a] -= 1
if need[a] == 0:
ready.append(a)
# a cycle leaves some courses stuck
return done == n
tests = [(2, [[1, 0]]),
(2, [[1, 0], [0, 1]]),
(4, [[1, 0], [2, 1], [3, 1]])]
for n, pre in tests:
ok = can_finish(n, pre)
print("true" if ok else "false")
$ python3 course_schedule.py
true
false
true