Task Execution Engine | Dataford Interview Questions

Design a Task Execution Engine that executes tasks based on dependency relationships while maximizing parallelism and minimizing worker idle time.

Asked in the Technical Screen stage. Implement an event-driven scheduler for a directed acyclic task graph.

Input and Output

Implement execute_tasks(tasks, worker_count). tasks is a dictionary mapping each task ID to an object with integer duration and a list of task IDs in dependencies. Return an object containing makespan and schedule, where each schedule entry has task, start, and end. Start all currently ready tasks whenever workers are available. Use lexicographic task ID order to break scheduling ties.

Constraints

The dependency graph is a directed acyclic graph.
1 <= len(tasks) <= 10^4
1 <= worker_count <= 10^4
1 <= duration <= 10^6
Task IDs are unique strings.
Every dependency refers to a task in tasks.

Function Signature

def execute_tasks(tasks, worker_count):

Your question is Task Execution Engine. 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