How should I practice Task Scheduler with Dependencies?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Scale AI online assessment problems in FastPrep.

Is Task Scheduler with Dependencies associated with Scale AI?

FastPrep tags this as a Scale AI coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Heap

Task Scheduler with Dependencies

Learn this problem

● HardScale AIFULLTIMEONSITE INTERVIEW

Problem statement

FastPrep turns the reported three-step interview progression into a runnable operation-list simulation: ADD models addTasks, CONSUME models consumeTask, and UPDATE models updateDeadline.

Core match: 85-90%. The main mechanics are preserved: earliest-deadline heap consume, subtask dependencies, deadline updates for unconsumed tasks, and stale heap entries skipped during consume.

Literal match: 80-85%. Since the source was a short interview recap, FastPrep made the runnable details explicit, including "NONE" when no task is available, tie-breaking by taskId, integer deadline comparison, unique task ids, no cycles, constraints, and extra corner-case examples.

Original Interview Progression

Part 1: Implement addTasks and consumeTask when there are no dependencies. consumeTask should return the available task with the earliest deadline.
Part 2: Extend the scheduler so a task may list subtasks. The task can be consumed only after every subtask has been consumed.
Part 3: Add updateDeadline(taskId, newDeadline). If the task has not been consumed, its deadline can change. consumeTask must ignore stale priority entries created before the update.

Problem Statement

You are implementing a task scheduler. Each task has a unique taskId, an integer deadline, and zero or more subtasks. A task with subtasks cannot be consumed until every listed subtask has already been consumed.

Simulate the scheduler with an operation list and return the result of every CONSUME operation.

Function Signature

public List<String> processOperations(List<List<String>> operations)

Operation Format

["ADD", taskId, deadline]
["ADD", taskId, deadline, subtask1, subtask2, ...]
["CONSUME"]
["UPDATE", taskId, newDeadline]

Rules

A task can be consumed at most once.
A task is available only after all of its subtasks have already been consumed.
A referenced subtask may be added before or after the task that depends on it.
If a referenced subtask is never added and consumed, the parent task remains unavailable.
Among available tasks, CONSUME returns the task with the smallest current deadline.
Deadlines are encoded as strings in the input, but they must be compared as integers.
If multiple available tasks have the same deadline, return the lexicographically smaller taskId.
If no task is available when CONSUME is called, return "NONE".
UPDATE has no effect if the task does not exist or has already been consumed.
Updating a blocked but unconsumed task is allowed. Its new deadline should be used once it becomes available.
Each taskId is added at most once. You may assume there are no cyclic dependencies.

Function

processOperations(operations: List<List<String>>) → List<String>

Examples

Example 1

operations = [["ADD", "A", "5"], ["ADD", "B", "2"], ["CONSUME"], ["CONSUME"]]return = ["B", "A"]

Both tasks are available immediately. Task B has the earlier deadline.

Example 2

operations = [["ADD", "A", "5"], ["ADD", "B", "2"], ["ADD", "C", "1", "A", "B"], ["CONSUME"], ["CONSUME"], ["CONSUME"]]return = ["B", "A", "C"]

C has the smallest deadline, but it depends on A and B, so it cannot be consumed until both are done.

Example 3

operations = [["ADD", "A", "5"], ["ADD", "B", "2"], ["UPDATE", "B", "10"], ["CONSUME"], ["CONSUME"]]return = ["A", "B"]

B was available with deadline 2, then its deadline changes to 10. The scheduler must not consume the stale old heap entry for B.

Example 4

operations = [["ADD", "A", "10"], ["ADD", "B", "5", "A"], ["UPDATE", "B", "1"], ["CONSUME"], ["CONSUME"]]return = ["A", "B"]

The update to B is valid because B has not been consumed, but B remains blocked until A is consumed.

Example 5

operations = [["ADD", "C", "9"], ["ADD", "A", "9"], ["ADD", "B", "10"], ["CONSUME"], ["CONSUME"], ["CONSUME"]]return = ["A", "C", "B"]

Deadlines are parsed as integers, so 9 is before 10. Between A and C with the same deadline, A is returned first.

Example 6

operations = [["ADD", "A", "3", "B"], ["CONSUME"], ["ADD", "C", "1"], ["CONSUME"], ["CONSUME"]]return = ["NONE", "C", "NONE"]

A depends on B. Since B is never added and consumed, A never becomes available.

Constraints

1 <= operations.length <= 100000
1 <= number of added tasks <= 100000
0 <= total number of subtask references <= 200000
1 <= deadline <= 1000000000
taskId is a non-empty alphanumeric string with length at most 32.
Each taskId appears in ADD at most once.
The dependency graph has no cycles.