Course Scheduling with Topological Sort | Dataford Interview Questions

Topological sort: course scheduling like LeetCode 1136 (Parallel Courses); follow-up: which available courses to pick each semester (under a limit).

Asked in the phone screen stage. Commenter suggests BFS/queue approach suits follow-ups.

Implement schedule_courses(n, relations, k). Courses are numbered 1 through n; each relation [a, b] means course a must be completed before b. Each semester, select at most k currently available courses, choosing the smallest course numbers first. Return a list of semester lists. Return [] if prerequisites contain a cycle.

Example 1: n=4, relations=[[1,3],[2,3],[3,4]], k=2 returns [[1,2],[3],[4]].

Example 2: n=3, relations=[[1,2],[2,3]], k=2 returns [[1],[2],[3]].

Constraints: 1 <= n <= 10^4, 0 <= len(relations) <= 2*10^4, 1 <= k <= n, and prerequisite pairs contain distinct valid course IDs.

Constraints

1 <= n <= 10^4
0 <= len(relations) <= 2 * 10^4
1 <= k <= n
Each relation is [prerequisite, course]
Course IDs are integers from 1 through n
Each prerequisite pair contains distinct course IDs

Function Signature

def schedule_courses(n, relations, k):

Your question is Course Scheduling with Topological Sort. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem