Task Scheduler with Dependencies
Updated
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
addTasksandconsumeTaskwhen there are no dependencies.consumeTaskshould 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.consumeTaskmust 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,
CONSUMEreturns 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
CONSUMEis called, return"NONE". UPDATEhas 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
taskIdis 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 <= 1000001 <= number of added tasks <= 1000000 <= total number of subtask references <= 2000001 <= deadline <= 1000000000taskIdis a non-empty alphanumeric string with length at most32.- Each
taskIdappears inADDat 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