ETL Dependency Orchestration
ETL Dependency Orchestration
ETL pipelines consist of tasks with dependencies between them, forming a directed acyclic graph (DAG). An orchestrator must schedule tasks so that dependencies are respected, while utilizing available resources efficiently through parallel execution.
Given a set of tasks with durations, resource costs, and dependency lists, produce a schedule that assigns a start time to each task.
Scheduling Algorithm
At each point in time:
-
Complete any tasks whose end time has been reached
-
Identify ready tasks: all dependencies completed, not yet started or running
-
Sort ready tasks alphabetically by name
-
Greedily assign tasks in that order, skipping any that would exceed the resource budget (sum of resources of all currently running tasks + new task must not exceed budget)
-
Advance time to the next task completion event
Return a list of tuples (task_name, start_time) sorted by (start_time, task_name).
Examples
Input:
tasks = [ {"name": "extract", "duration": 2, "resources": 1, "depends_on": []}, {"name": "transform", "duration": 3, "resources": 1, "depends_on": ["extract"]}, {"name": "load", "duration": 1, "resources": 1, "depends_on": ["transform"]}, ] resource_budget = 2
Output:
[("extract", 0), ("transform", 2), ("load", 5)]
Linear chain: each task waits for the previous one to finish.
Input:
tasks = [ {"name": "fetch_orders", "duration": 3, "resources": 1, "depends_on": []}, {"name": "fetch_users", "duration": 2, "resources": 1, "depends_on": []}, {"name": "join", "duration": 1, "resources": 2, "depends_on": ["fetch_users", "fetch_orders"]}, ] resource_budget = 2
Output:
[("fetch_orders", 0), ("fetch_users", 0), ("join", 3)]
Both fetch tasks run in parallel (1+1=2 <= budget). Join starts after the slower one (fetch_orders) finishes at time 3.
Hint 1
Track running tasks with their end times. At each step, complete all tasks whose end time has been reached.
Hint 2
A task that does not fit the current resource budget is skipped, but later tasks in the ready queue might still fit.
Requirements
- Respect all dependency constraints before scheduling a task
- Never exceed the resource budget at any point in time
- Use alphabetical ordering to break ties among ready tasks
- Advance time by jumping to the next task completion, not one unit at a time
Constraints
- 1 <= len(tasks) <= 100
- duration >= 1, resources >= 1
- The task graph is a valid DAG (no cycles)
- Every task's resources <= resource_budget (each task is individually schedulable)
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number
ETL Dependency Orchestration
ETL Dependency Orchestration
ETL pipelines consist of tasks with dependencies between them, forming a directed acyclic graph (DAG). An orchestrator must schedule tasks so that dependencies are respected, while utilizing available resources efficiently through parallel execution.
Given a set of tasks with durations, resource costs, and dependency lists, produce a schedule that assigns a start time to each task.
Scheduling Algorithm
At each point in time:
-
Complete any tasks whose end time has been reached
-
Identify ready tasks: all dependencies completed, not yet started or running
-
Sort ready tasks alphabetically by name
-
Greedily assign tasks in that order, skipping any that would exceed the resource budget (sum of resources of all currently running tasks + new task must not exceed budget)
-
Advance time to the next task completion event
Return a list of tuples (task_name, start_time) sorted by (start_time, task_name).
Examples
Input:
tasks = [ {"name": "extract", "duration": 2, "resources": 1, "depends_on": []}, {"name": "transform", "duration": 3, "resources": 1, "depends_on": ["extract"]}, {"name": "load", "duration": 1, "resources": 1, "depends_on": ["transform"]}, ] resource_budget = 2
Output:
[("extract", 0), ("transform", 2), ("load", 5)]
Linear chain: each task waits for the previous one to finish.
Input:
tasks = [ {"name": "fetch_orders", "duration": 3, "resources": 1, "depends_on": []}, {"name": "fetch_users", "duration": 2, "resources": 1, "depends_on": []}, {"name": "join", "duration": 1, "resources": 2, "depends_on": ["fetch_users", "fetch_orders"]}, ] resource_budget = 2
Output:
[("fetch_orders", 0), ("fetch_users", 0), ("join", 3)]
Both fetch tasks run in parallel (1+1=2 <= budget). Join starts after the slower one (fetch_orders) finishes at time 3.
Hint 1
Track running tasks with their end times. At each step, complete all tasks whose end time has been reached.
Hint 2
A task that does not fit the current resource budget is skipped, but later tasks in the ready queue might still fit.
Requirements
- Respect all dependency constraints before scheduling a task
- Never exceed the resource budget at any point in time
- Use alphabetical ordering to break ties among ready tasks
- Advance time by jumping to the next task completion, not one unit at a time
Constraints
- 1 <= len(tasks) <= 100
- duration >= 1, resources >= 1
- The task graph is a valid DAG (no cycles)
- Every task's resources <= resource_budget (each task is individually schedulable)
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number