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 medium 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 Task Processor | Scale AI Coding Question

Quick Overview

This question evaluates understanding of priority-based scheduling and dependency resolution, focusing on data structures and graph-ordering concepts required to retrieve the smallest-deadline task while respecting prerequisite subtasks.

Implement a Task Processor

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a task processor that supports two operations: - `AddTask(task)`: add a new task. - `ConsumeTask()`: remove and return the `id` of the next task to execute. Each task has: - `id`: a unique integer - `deadline`: an integer priority, where a smaller value means the task should be consumed earlier - `subtasks` (optional): a list of task IDs that must be consumed before this task can be consumed Implement the processor in two stages: **Part 1** Ignore `subtasks`. `ConsumeTask()` should always return the ID of the unconsumed task with the smallest deadline. **Part 2** Now each task may include a `subtasks` field. A task is eligible to be consumed only after all tasks listed in its `subtasks` have already been consumed. Among all currently eligible tasks, `ConsumeTask()` should return the one with the smallest deadline. Assume tasks may be added in any order. If multiple eligible tasks have the same deadline, return the one with the smaller `id`. If no task is currently eligible, return `null`. Example: - Add task `{id: 1, deadline: 2, subtasks: [2]}` - Add task `{id: 2, deadline: 4, subtasks: []}` Then the consume order should be `2`, then `1`, because task `1` depends on task `2`.

Quick Answer: This question evaluates understanding of priority-based scheduling and dependency resolution, focusing on data structures and graph-ordering concepts required to retrieve the smallest-deadline task while respecting prerequisite subtasks.

Part 1: Task Processor Without Dependencies

Implement a task processor for a sequence of operations. Each task has a unique `id` and an integer `deadline`. In this part, ignore any `subtasks` information completely. For every `consume` operation, remove and return the `id` of the unconsumed task with the smallest deadline. If multiple tasks have the same deadline, return the smaller `id` first. If there is no available task, return `None` for that consume operation. Your function should process all operations in order and return a list containing the result of each `consume`.

Constraints

0 <= len(operations) <= 200000
Each task id is unique across all add operations
0 <= deadline <= 10^9
The number of consume operations can be larger than the number of added tasks

Examples

Input: [('add', {'id': 10, 'deadline': 5}), ('add', {'id': 2, 'deadline': 3}), ('add', {'id': 7, 'deadline': 3}), ('consume',), ('consume',), ('consume',)]

Expected Output: [2, 7, 10]

Explanation: Tasks with deadline 3 are consumed before deadline 5, and id 2 comes before id 7 on the tie.

Loading coding console...

Part 2: Task Processor With Subtask Dependencies

Implement a task processor for a sequence of operations. Each task has a unique `id`, an integer `deadline`, and an optional list `subtasks` containing task ids that must be consumed first. A task is eligible to be consumed only when all task ids listed in its `subtasks` have already been consumed. Among all currently eligible tasks, `consume` must remove and return the task with the smallest deadline. If multiple eligible tasks have the same deadline, return the smaller `id`. If no task is currently eligible, return `None`. Tasks may be added in any order, including before the tasks they depend on are added. Your function should process all operations in order and return a list containing the result of each `consume`.

Constraints

0 <= len(operations) <= 200000
Each task id is unique across all add operations
0 <= deadline <= 10^9
The total number of subtask references across all added tasks is at most 200000
Each task's subtasks list contains distinct ids
Subtasks may reference tasks added later, and dependency cycles may exist

Examples

Input: [('add', {'id': 1, 'deadline': 2, 'subtasks': [2]}), ('add', {'id': 2, 'deadline': 4, 'subtasks': []}), ('consume',), ('consume',), ('consume',)]

Expected Output: [2, 1, None]

Explanation: Task 1 is blocked until task 2 is consumed.

Input: [('add', {'id': 1, 'deadline': 2, 'subtasks': []}), ('add', {'id': 3, 'deadline': 2, 'subtasks': []}), ('add', {'id': 2, 'deadline': 1, 'subtasks': [3]}), ('consume',), ('consume',), ('consume',)]

Expected Output: [1, 3, 2]

Explanation: Task 2 has the smallest deadline but is blocked. Between eligible tasks 1 and 3, the smaller id is consumed first.

Input: [('add', {'id': 1, 'deadline': 1, 'subtasks': [2]}), ('add', {'id': 2, 'deadline': 2, 'subtasks': [1]}), ('consume',)]

Expected Output: [None]

Explanation: Both tasks are blocked by a cycle, so nothing is eligible.

Input: [('add', {'id': 5, 'deadline': 10, 'subtasks': [6]}), ('consume',), ('add', {'id': 6, 'deadline': 1, 'subtasks': []}), ('consume',), ('consume',)]

Expected Output: [None, 6, 5]

Explanation: The first consume fails because task 5 depends on task 6, which is added later.

Input: []

Expected Output: []

Explanation: No operations means no consume results.

Hints

Track how many prerequisites each added task still needs before it becomes eligible.
Use a min-heap for eligible tasks, and when a task is consumed, update every task waiting on it.