FastPrepTask Processor: Dependencies and Deadlines

Task Processor: Dependencies and Deadlines

Scale AI logoScale AI● MediumFULLTIMENEW GRADPHONE SCREEN

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 subtasks appears in taskIds.
  • The dependency graph is a DAG.
  • Use a min-heap or priority queue for currently eligible tasks.

More Scale AI Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Scale AI interview experiences

All Scale AI interview questionsSee Scale AI hiring insights
Saved
class Solution {
    public String[] consumeTasks(String[] taskIds, int[] deadlines, String[][] subtasks) {
      // write your code here
    }
}
Checking account…