Thread-Safe Task Scheduler | Dataford Interview Questions

Your question is Thread-Safe Task Scheduler. Start with the requirements on the right.

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

Problem

Publicis Sapient's Sapient Slingshot orchestration layer needs to run background jobs in parallel, but a job may start only after all of its dependencies finish. Implement a scheduler that simulates this multithreaded execution and returns the order in which jobs start.

A job is represented by an integer 0..n-1. You are given dependency pairs [a, b] meaning job b depends on job a, so a must complete before b can begin. At most worker_count jobs can run at the same time. When multiple jobs are ready, always start the smaller job id first. Each job takes exactly 1 time unit, and all jobs that start in the same time unit complete together at the end of that unit.

Return a list of lists, where each inner list contains the job ids started in one time unit. If all jobs cannot be completed because of a cycle, return an empty list.

Constraints

1 <= n <= 10^5
0 <= len(dependencies) <= 2 * 10^5
1 <= worker_count <= n
0 <= a, b < n
a != b

Function Signature

def synchronized_schedule(n, dependencies, worker_count):

Your question is Thread-Safe Task Scheduler. Start with the requirements on the right.

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

Return a list of lists, where each inner list contains the job ids started in one time unit. If all jobs cannot be completed because of a cycle, return an empty list.

Constraints

1 <= n <= 10^5
0 <= len(dependencies) <= 2 * 10^5
1 <= worker_count <= n
0 <= a, b < n
a != b

Function Signature

def synchronized_schedule(n, dependencies, worker_count):