Task Dependency - Parallel Execution Levels

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Description

You are given a Tasks table and a Dependencies table. A task can only start after all tasks it depends on have completed. Tasks with no dependencies can run immediately (level 1). Write a SQL query to assign an execution_level to each task: the earliest level at which it can run, given all its dependencies must be at a strictly lower level. Return (task_id, execution_level) ordered by execution_level, then task_id. Table: Tasks

Column Name	Type	Description
task_id	INT	Primary key
task_name	VARCHAR	Name of task

Table: Dependencies

Column Name	Type	Description
task_id	INT	Task that depends on another
depends_on	INT	Task that must complete first

Database Schema (Inferred)

Tasks

Column Name	Example Value
task_id	1
task_name	T1

Dependencies

Column Name	Example Value
task_id	3
depends_on	1

Example

Tasks

task_id	task_name
1	T1
2	T2
3	T3
4	T4
5	T5
6	T6

Dependencies

task_id	depends_on
3	1
3	2
4	2
5	3
6	4
6	5

Output

task_id	execution_level
1	1
2	1
3	2
4	2
5	3
6	4

Explanation:

T1, T2 have no deps → level 1. T3 depends on T1(1) and T2(1) → level 2. T4 depends on T2(1) → level 2. T5 depends on T3(2) → level 3. T6 depends on T4(2) and T5(3) → level 4. Use recursive CTE propagating level from roots and take MAX per task.

Approach hint

Start with a simple approach, explain the trade-off, then move toward a cleaner or more scalable solution.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.