FastPrepTask Scheduler with Dependencies
Problems/Task Scheduler with Dependencies

Task Scheduler with Dependencies

Scale AI logoScale AI● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

The three parts become an operation-list simulation: ADD models addTasks, CONSUME models consumeTask, and UPDATE models updateDeadline.

The simulation covers the main mechanics: earliest-deadline heap consume, subtask dependencies, deadline updates for unconsumed tasks, and stale heap entries skipped during consume.

Runnable details: return "NONE" when no task is available, break ties by taskId, and compare deadlines as integers. Task ids are unique and there are no cycles.

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.

More Scale AI Onsite Interview questions

  • Best Poker Category with a JokerPHONE SCREEN · ONSITE INTERVIEW · Seen Jun 2026
  • Format and Validate a Model ResponseONSITE INTERVIEW · Seen Apr 2026
  • Stateful Neuron Matrix UpdateONSITE INTERVIEW · Seen Apr 2026
  • Clock Hand Angle with Subsecond PrecisionONSITE INTERVIEW · Seen Dec 2025
  • Four-Player Matching Card GameONSITE INTERVIEW · Seen Feb 2025
  • Rotate an Array to the RightONSITE INTERVIEW · Seen Oct 2024
  • Rich-Text Segment Normalization and Bold ToggleONSITE INTERVIEW · Seen Apr 2024
  • Minimum Distance Matching in a ForestPHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2024
  • Shortest Distance Between Two NodesONSITE INTERVIEW · Seen Jan 2024
  • Fit Beta Parameters by Maximum LikelihoodONSITE INTERVIEW · Seen Sep 2022

Similar questions at other companies

  • 15-Minute Chat Session TrackerOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
  • Top K Upvoted Songs by ArtistAmazon · ONSITE INTERVIEW
  • LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions
  • Dynamic Median with Additions and DeletionsByteDance · ONSITE INTERVIEWByteDance interview questions
  • Tiered Expiring Item StoreHudson River Trading · PHONE SCREEN · ONSITE INTERVIEWHudson River Trading interview questions
  • Thread-Safe LRU Cache with TTLLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Top K Frequent Elements After Each Stream UpdateSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Trade Volume LeaderboardBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Design Authentication ManagerOracle · ONSITE INTERVIEWOracle interview questions
  • Lowest-Bid Auction SystemGoogle · ONSITE INTERVIEWGoogle interview questions

Scale AI interview experiences

  • Scale AI Forward Deployed Engineer Debugging Round: 1 Experience
  • Scale AI ML Research Engineering Intern Interviews: 1 Experience
  • Scale AI SWE Intern Debugging Interview: 9 Experiences
  • Scale AI New Grad SWE and MLE Question Bank
  • Scale AI New Grad SWE Poker Screen and Onsite: 1 Experience
  • Scale AI New Grad SWE OA Questions: 1 Experience
All Scale AI interview questionsSee Scale AI hiring insights
Saved
class Solution {
    public List<String> processOperations(List<List<String>> operations) {
      // write your code here
    }

}
Checking account…