Implement a Dependency-Aware Task Scheduler
Company: Scale AI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Implement a `TaskManager` class with two methods:
- `AddTasks(tasks)`: add one or more tasks into the system.
- `ConsumeTask()`: return and remove the executable task with the earliest deadline.
Each task has the following fields:
- `id`: unique task identifier
- `ddl`: integer deadline, where a smaller value means an earlier deadline
- `subTasks`: a list of prerequisite task IDs that must be completed before this task can be consumed
Requirements:
1. Support multiple calls to `AddTasks`.
2. `ConsumeTask()` should return the pending task with the smallest deadline among all currently executable tasks.
3. A task is executable only if all of its prerequisite tasks have already been consumed.
4. If no executable task exists, return `NO_TASK`.
5. For this coding problem, assume task IDs are unique and the dependency graph is valid and acyclic.
Explain the data structures you would use and implement both methods efficiently.
Quick Answer: This question evaluates skills in dependency management, deadline-driven scheduling and algorithmic data-structure design, focusing on handling directed acyclic graphs and ordering constraints.
Design a dependency-aware task scheduler. Each task has an integer `id`, an integer deadline `ddl`, and a list `subTasks` containing prerequisite task IDs. A task can be consumed only after all of its prerequisite tasks have already been consumed.
The original interface is a `TaskManager` class with:
- `AddTasks(tasks)`: add one or more new tasks
- `ConsumeTask()`: return and remove the currently executable task with the earliest deadline
For this judge, implement a function `solution(operations)` that simulates the class.
Each operation is one of:
- `('add', tasks)` where `tasks` is a list of task dictionaries
- `('consume',)`
For every `('consume',)` operation, append the returned value to the answer list.
Rules:
1. Multiple add operations are allowed.
2. A task is executable only if every ID in `subTasks` has already been consumed.
3. Among executable tasks, consume the one with the smallest `ddl`.
4. If several executable tasks have the same `ddl`, consume the one with the smaller `id`.
5. If no executable task exists, return `'NO_TASK'`.
6. Task IDs are unique, and the dependency graph is valid and acyclic.
Return a list containing the result of every consume operation in order.
Constraints
- 1 <= total number of tasks across all add operations <= 200000
- 0 <= total number of dependency links across all tasks <= 200000
- 0 <= ddl <= 10^9
- Task IDs are unique integers
- The dependency graph is acyclic and all prerequisite IDs are valid task IDs that may appear in earlier or later add operations