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.
