PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates skills in designing and implementing data structures and algorithms for priority scheduling, dependency resolution, and dynamic updates, encompassing priority queues, graph-based dependency tracking, and state management.

  • hard
  • Scale AI
  • Coding & Algorithms
  • Software Engineer

Implement Dependency-Aware Task Scheduler

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design and implement a task scheduler that supports adding tasks and consuming executable tasks in deadline order. Each task has: - `taskId`: a unique identifier - `deadline`: an integer deadline; smaller values mean higher priority - `subtasks`: a list of task IDs that must be consumed before this task can be consumed Implement the following API incrementally: ### Part 1: No dependencies Implement: ```text addTasks(tasks) consumeTask() -> taskId or null ``` For Part 1, each task is represented as `(taskId, deadline)` and has no dependencies. `consumeTask()` should return and remove the unconsumed task with the smallest deadline. If multiple tasks have the same deadline, return the one with the smaller `taskId`. If no task is available, return `null`. ### Part 2: Dependencies Extend `addTasks` so each task is represented as `(taskId, deadline, subtasks)`. A task is only eligible to be consumed after all of its `subtasks` have already been consumed. Among all currently eligible tasks, `consumeTask()` should still return the task with the smallest deadline, breaking ties by smaller `taskId`. Tasks may be added in batches. Dependencies are given by task ID. If a dependency has already been consumed, it should be treated as satisfied. A task that is added but whose dependencies are not yet satisfied should become eligible automatically once its final dependency is consumed. ### Part 3: Deadline updates Add: ```text updateDeadline(taskId, newDeadline) ``` If the task exists and has not yet been consumed, update its deadline to `newDeadline`. If the task is already consumed or does not exist, the call should have no effect. After deadline updates, `consumeTask()` must still return the currently eligible unconsumed task with the smallest latest deadline.

Quick Answer: This question evaluates skills in designing and implementing data structures and algorithms for priority scheduling, dependency resolution, and dynamic updates, encompassing priority queues, graph-based dependency tracking, and state management.

Part 1: Schedule Tasks by Deadline

Simulate a task scheduler with no dependencies. You are given a sequence of operations. Each `add` operation inserts a batch of tasks, where every task is `[taskId, deadline]`. Each `consume` operation must remove the unconsumed task with the smallest deadline. If several tasks share the same deadline, consume the one with the smaller `taskId` first. Return the results of all `consume` operations in order, using `-1` when no task is available.

Constraints

  • `0 <= len(operations) <= 2 * 10^5`
  • `len(add_batches) == len(operations)`
  • The total number of tasks across all add operations is at most `2 * 10^5`
  • `1 <= taskId <= 10^9`
  • `0 <= deadline <= 10^9`
  • All `taskId` values are unique across all added tasks

Examples

Input: (['add', 'consume', 'consume'], [[[10, 5], [3, 2], [7, 2]], [], []])

Expected Output: [3, 7]

Explanation: Tasks 3 and 7 share the smallest deadline 2, so task 3 is consumed first because it has the smaller taskId.

Input: (['add', 'consume', 'add', 'consume', 'consume'], [[[1, 4], [2, 6]], [], [[3, 1]], [], []])

Expected Output: [1, 3, 2]

Explanation: After consuming task 1, a new earlier-deadline task 3 is added and should be consumed next.

Input: (['consume', 'add', 'consume', 'consume'], [[], [[5, 10]], [], []])

Expected Output: [-1, 5, -1]

Explanation: The first and last consume operations happen when the scheduler is empty.

Input: (['add', 'consume'], [[], []])

Expected Output: [-1]

Explanation: An empty add batch changes nothing, so the consume operation returns -1.

Hints

  1. Use a min-heap keyed by `(deadline, taskId)` so the next task is always on top.
  2. You only need to return values for `consume` operations, not for `add` operations.

Part 2: Dependency-Aware Task Consumption

Extend the scheduler so tasks may depend on other tasks. You are given a sequence of operations. Each `add` operation inserts a batch of tasks, where every task is encoded as `[taskId, deadline, dep1, dep2, ...]`. A task becomes eligible only after all of its dependency task IDs have already been consumed. Among currently eligible tasks, `consume` must choose the one with the smallest deadline, breaking ties by smaller `taskId`. Dependencies may refer to tasks added earlier, later, or never added. Return the results of all `consume` operations in order, using `-1` when no eligible task exists.

Constraints

  • `0 <= len(operations) <= 2 * 10^5`
  • `len(add_batches) == len(operations)`
  • The total number of tasks across all add operations is at most `2 * 10^5`
  • The total number of dependency references across all tasks is at most `2 * 10^5`
  • `1 <= taskId <= 10^9`
  • `0 <= deadline <= 10^9`
  • All `taskId` values are unique across all added tasks
  • Within a single task, dependency IDs are distinct

Examples

Input: (['add', 'consume', 'consume', 'consume'], [[[1, 5], [2, 2, 1], [3, 2]], [], [], []])

Expected Output: [3, 1, 2]

Explanation: Tasks 1 and 3 are initially eligible; task 3 is consumed first due to earlier deadline. Consuming task 1 then unlocks task 2.

Input: (['add', 'consume', 'add', 'consume', 'consume'], [[[10, 3, 20]], [], [[20, 1]], [], []])

Expected Output: [-1, 20, 10]

Explanation: Task 10 is blocked by task 20, which is added later. The first consume finds nothing eligible.

Input: (['add', 'consume', 'add', 'consume'], [[[1, 5]], [], [[2, 1, 1]], []])

Expected Output: [1, 2]

Explanation: When task 2 is added, its dependency task 1 has already been consumed, so task 2 is immediately eligible.

Input: (['add', 'consume', 'consume', 'consume'], [[[5, 4], [4, 4], [6, 3, 4]], [], [], []])

Expected Output: [4, 6, 5]

Explanation: Tasks 4 and 5 tie on deadline, so 4 is consumed first. That unlocks task 6 with deadline 3, which then comes before task 5.

Hints

  1. Track how many dependencies of each task are still unsatisfied.
  2. Also build a reverse mapping from a dependency ID to the tasks waiting on it, so one consume can unlock other tasks.

Part 3: Dependency-Aware Scheduler with Deadline Updates

Now support deadline changes. You are given a sequence of operations. Each `add` operation inserts a batch of tasks, where every task is `[taskId, deadline, dep1, dep2, ...]`. Each `update` operation is `[taskId, newDeadline]` and changes the deadline only if that task exists and has not been consumed. Each `consume` operation must remove the currently eligible task with the smallest latest deadline, breaking ties by smaller `taskId`. If a blocked task gets updated, its new deadline should be used once it becomes eligible. Return the results of all `consume` operations in order, using `-1` when no eligible task exists.

Constraints

  • `0 <= len(operations) <= 2 * 10^5`
  • `len(add_batches) == len(operations)`
  • `len(updates) == len(operations)`
  • The total number of tasks across all add operations is at most `2 * 10^5`
  • The total number of dependency references across all tasks is at most `2 * 10^5`
  • The total number of update operations is at most `2 * 10^5`
  • `1 <= taskId <= 10^9`
  • `0 <= deadline, newDeadline <= 10^9`
  • All `taskId` values are unique across all added tasks
  • Within a single task, dependency IDs are distinct

Examples

Input: (['add', 'update', 'consume', 'consume'], [[[1, 5], [2, 3]], [], [], []], [[], [1, 1], [], []])

Expected Output: [1, 2]

Explanation: Task 1 is updated to an earlier deadline and should be consumed before task 2.

Input: (['add', 'update', 'consume', 'consume', 'consume'], [[[1, 5, 2], [2, 4]], [], [], [], []], [[], [1, 1], [], [], []])

Expected Output: [2, 1, -1]

Explanation: Task 1 is blocked when updated, but its new deadline 1 is used once task 2 is consumed and task 1 becomes eligible.

Input: (['add', 'consume', 'update', 'update', 'consume'], [[[1, 2]], [], [], [], []], [[], [], [1, 10], [9, 1], []])

Expected Output: [1, -1]

Explanation: Updating a consumed task or a task that does not exist has no effect.

Input: (['add', 'update', 'update', 'consume', 'consume'], [[[1, 5], [2, 5]], [], [], [], []], [[], [2, 1], [2, 7], [], []])

Expected Output: [1, 2]

Explanation: Task 2 gets two updates. The stale heap entry for deadline 1 must be ignored because the latest deadline is 7.

Input: (['add', 'update', 'add', 'consume', 'consume'], [[[10, 5, 20]], [], [[20, 2]], [], []], [[], [10, 1], [], [], []])

Expected Output: [20, 10]

Explanation: Task 10 is updated while blocked on task 20. After task 20 is consumed, task 10 becomes eligible with its updated deadline.

Hints

  1. A min-heap still helps, but an updated task may already have an old entry in the heap. Consider lazy deletion.
  2. When a blocked task becomes eligible, push its current deadline, not its original one.
Last updated: Jun 6, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Dependency-Aware Task Scheduler - Scale AI (easy)
  • Schedule Ready Tasks by Deadline - Scale AI (medium)
  • Implement a Task Processor - Scale AI (medium)
  • Update a Neuron Grid - Scale AI (medium)
  • Implement multi-head attention and LLM sampling - Scale AI (easy)