Task Processor: Dependencies and Deadlines
Updated
Problem statement
You are building a task processor. Each task has a string id, an integer deadline, and a list of subtasks that must be consumed before the task itself can be consumed.
Given all tasks up front, repeatedly consume one eligible task until no tasks remain. A task is eligible when all of its subtasks have already been consumed. Among all eligible tasks, always consume the task with the smallest deadline. If multiple eligible tasks have the same deadline, consume the lexicographically smaller task id first.
Return the ids of the tasks in the order they are consumed.
Function
consumeTasks(taskIds: String[], deadlines: int[], subtasks: String[][]) → String[]Examples
Example 1
taskIds = ["1", "2"]deadlines = [2, 4]subtasks = [["2"], []]return = ["2", "1"]Task 1 has the earlier deadline, but it depends on task 2, so task 2 must be consumed first.
Example 2
taskIds = ["a", "b", "c"]deadlines = [5, 1, 3]subtasks = [[], [], []]return = ["b", "c", "a"]With no dependencies, tasks are consumed by increasing deadline.
Constraints
taskIds.length == deadlines.length == subtasks.length- Task ids are unique non-empty strings.
- Every id listed in
subtasksappears intaskIds. - The dependency graph is a DAG.
- Use a min-heap or priority queue for currently eligible tasks.
More Scale AI Phone Screen questions
- Four-Player Trick-Taking Card Game SimulationOA · PHONE SCREEN · Seen Aug 2026
- Best Poker Category with a JokerPHONE SCREEN · ONSITE INTERVIEW · Seen Jun 2026
- Free Time for Every Meeting RoomPHONE SCREEN · Seen Apr 2026
- Free Windows Between Busy IntervalsOA · PHONE SCREEN · Seen Apr 2026
- Order Queries by Shortest Processing TimePHONE SCREEN · Seen Apr 2026
- Party Time by Town and Quiet Gaps by CityPHONE SCREEN · Seen Jan 2026
- Party Windows and Dead Zone TimePHONE SCREEN · Seen Oct 2025
- Overlap Duration of Two Time IntervalsPHONE SCREEN · Seen Jun 2025
- Multi-Head Attention BlockPHONE SCREEN · Seen Mar 2025
- Top-K SamplerPHONE SCREEN · Seen Mar 2025
Similar questions at other companies
- Task Scheduler with Prerequisites and Execution PathsBrex · PHONE SCREEN
- Course Ordering with Concurrent UpdatesNuro · PHONE SCREENNuro interview questions
- Streaming Median of Trade PricesXantium · PHONE SCREEN
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Dependency-Aware Task SchedulerRippling · PHONE SCREENRippling interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Alert Engine with a Repeat IntervalChronosphere · PHONE SCREEN
- Lexicographically Smallest Topological OrderByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Merge Subsequences Into a Consistent Total OrderGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions