How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Scale AI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Scale AI during technical interviews.

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.

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

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

Explanation: Task 2 is added before its prerequisite task 1, so the first consume finds nothing executable. After task 1 is added and consumed, task 2 becomes executable.

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

Expected Output: [1, 2, 3]

Explanation: Task 1 is consumed before task 3 is added. Since task 3 depends only on 1, it is immediately executable when added. Task 2 still goes first because it has the smaller deadline.

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

Expected Output: [1, 3, 4]

Explanation: All tasks are executable with the same deadline, so ties are broken by smaller task ID.

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

Expected Output: [2, 4, 1, 3, 5]

Explanation: Task 2 is consumed first, unlocking 4. After 1 is later consumed, task 3 becomes executable. Once both 3 and 4 are done, task 5 is unlocked.

Input: []

Expected Output: []

Explanation: No operations means there are no consume results to return.

Hints

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.
Track, for each task, how many prerequisites are still unfinished, and keep reverse edges from each prerequisite to the tasks that depend on it.

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.