How should I practice Task Scheduler with Prerequisites and Execution Paths?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Brex phone screen problems in FastPrep.

Is Task Scheduler with Prerequisites and Execution Paths associated with Brex?

FastPrep tags this as a Brex phone screen coding practice problem when the problem catalog has that company and stage context.

Task Scheduler with Prerequisites and Execution Paths

Brex● MediumFULLTIMEPHONE SCREEN

Problem statement

Build a task scheduler. It starts empty. Process operations in order; taskIds[i] and prerequisites[i] hold the values for operations[i].

Each task is waiting, running or completed. A task is ready when it is waiting and all of its prerequisites are completed.

"addTask": add a waiting task taskIds[i] whose prerequisites are prerequisites[i]. A task with no prerequisites is ready right away.
"getNextTask": hand out the ready task that was added earliest. It becomes running. Record a list with its id, or an empty list if no task is ready.
"completeTask": the running task taskIds[i] becomes completed. This can make other tasks ready.
"getExecutionPath": record the execution path for the target task taskIds[i]. This does not change any task.

The execution path holds the target and every task it depends on, directly or through other prerequisites, that is not completed yet. Running tasks are included. List them so that every task comes after its prerequisites: repeatedly take the task added earliest among those whose prerequisites are all completed or already listed. If the target is completed, the path is empty.

Return the recorded lists of all getNextTask and getExecutionPath operations, in order.

Function

runTaskScheduler(operations: String[], taskIds: String[], prerequisites: String[][]) → String[][]

Examples

Example 1

operations = ["addTask","addTask","getNextTask","getNextTask","getNextTask"]taskIds = ["build","test","","",""]prerequisites = [[],[],[],[],[]]return = [["build"],["test"],[]]

Part 1 has no prerequisites. getNextTask hands out build, then test, in the order they were added. The third call finds no waiting task and records an empty list.

Example 2

operations = ["addTask","addTask","addTask","getNextTask","getNextTask","getNextTask","completeTask","getNextTask"]taskIds = ["fetch","parse","lint","","","","fetch",""]prerequisites = [[],["fetch"],[],[],[],[],[],[]]return = [["fetch"],["lint"],[],["parse"]]

parse needs fetch. The first call hands out fetch. The second call skips parse, because fetch is not completed yet, and hands out lint. The third call finds nothing ready and records []. After fetch is completed, parse is ready and is handed out.

Example 3

operations = ["addTask","addTask","addTask","addTask","getExecutionPath","getNextTask","completeTask","getExecutionPath"]taskIds = ["a","b","c","d","d","","a","d"]prerequisites = [[],["a"],["a"],["c","b"],[],[],[],[]]return = [["a","b","c","d"],["a"],["b","c","d"]]

To run d, we need b and c, which both need a. In added order, the path is a, b, c, d. Then a is handed out and completed, so the second path leaves it out: b, c, d.

Constraints

1 <= operations.length <= 1000
taskIds.length == prerequisites.length == operations.length
Each operations[i] is "addTask", "getNextTask", "completeTask" or "getExecutionPath".
Task ids are 1 to 8 lowercase English letters, and no two addTask calls use the same id.
For addTask, prerequisites[i] has at most 5 different ids, and each one was added by an earlier addTask. For every other operation, prerequisites[i] is empty.
For getNextTask, taskIds[i] is the empty string.
completeTask is only called on a running task. getExecutionPath is only called on a task that was already added.