Quick Overview

This question evaluates skills in dependency management, deadline-driven scheduling and algorithmic data-structure design, focusing on handling directed acyclic graphs and ordering constraints.

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

Examples

Input: [('add', [{'id': 1, 'ddl': 5, 'subTasks': []}, {'id': 2, 'ddl': 3, 'subTasks': []}]), ('consume',), ('consume',), ('consume',)]

Expected Output: [2, 1, 'NO_TASK']

Explanation: Tasks 1 and 2 are immediately executable. Task 2 has the earlier deadline, then task 1, then nothing remains.

Input: [('add', [{'id': 1, 'ddl': 5, 'subTasks': []}, {'id': 2, 'ddl': 1, 'subTasks': [1]}, {'id': 3, 'ddl': 4, 'subTasks': []}]), ('consume',), ('consume',), ('consume',), ('consume',)]

Expected Output: [3, 1, 2, 'NO_TASK']

Explanation: Task 2 has the smallest deadline but is blocked by task 1. So task 3 is consumed first, then 1, which unlocks 2.

Hints

  1. You need one structure to quickly get the executable task with the smallest deadline, and another structure to update tasks that become executable after a prerequisite is consumed.
  2. Track, for each task, how many prerequisites are still unfinished, and keep reverse edges from each prerequisite to the tasks that depend on it.

Loading coding console...