Staged Task Scheduler: Dispatch Ready Tasks, Complete Them and Return an Execution Order
Company: Brex
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Implement an in-memory task scheduler as a class, and write your own tests for it. The interview is staged: there are three parts, and each one must work before the next is revealed. The first two parts introduce three operations, `addTask`, `getNextTask` and `completeTask`; the third adds `getExecutionPath`.
The report names the operations but not their exact contracts. This version assumes that a task may depend on other tasks and can run only after all of them are complete, which is what gives an execution path its meaning. The report also does not say how the first three operations were split across the first two parts; here Part 1 covers adding tasks and handing them out, and Part 2 covers completing them and the optimization follow-up. Confirm these contracts with the interviewer before coding.
### Clarifying Questions
- Does `addTask` take the task's dependencies, and may a dependency refer to a task that has not been added yet?
- Does `getNextTask` mark the returned task as running, so that it is not handed out twice, and what does it return when no task is ready?
- When several tasks are ready, must `getNextTask` return a particular one, for example the earliest added?
- What should happen for a duplicate task id, for completing a task that is unknown or not running, and for a dependency cycle?
### Part 1 — Add tasks and hand out the next ready task
Implement `addTask(taskId, dependencies)` and `getNextTask()`. A task is ready when every task it depends on is complete, and `getNextTask` returns a ready task that has not been handed out yet. Write tests showing that tasks without dependencies are handed out once each and that a task with an unfinished dependency is never handed out.
```hint Name the states
Decide which states a task moves through between being added and being finished, and which of them getNextTask may pick from.
```
#### What This Part Should Cover
- The task record and the containers that hold the tasks
- The readiness rule, including dependencies that have not been added yet
- The return value when nothing is ready, and tests written alongside the code
### Part 2 — Complete tasks and make the scheduler efficient
Implement `completeTask(taskId)`, which marks a running task as finished so that tasks waiting on it can become ready. Then answer the follow-up: a first version that keeps the tasks in a map plus a list and checks them on every call gets slower as tasks accumulate. How would you optimize it?
```hint Follow the work
Count what getNextTask examines after many tasks have finished, and ask what completeTask could do at the moment a task finishes so that later calls examine less.
```
#### What This Part Should Cover
- Correct state transitions, and errors for invalid completions
- The cost of each operation before and after the optimization
- Tests for chains and for tasks that depend on several others
### Part 3 — Return an execution path
Implement `getExecutionPath()`, which returns an order in which all the tasks can be executed so that every task appears after all of its dependencies. The order does not have to keep tasks in the order they were added.
```hint Who can go first
Think about which tasks could be placed first, and what changes for the remaining tasks once one of them is placed.
```
#### Clarifying Questions for this Part
- Should the path cover every task added, including those already completed, or only the remaining ones?
- If the dependencies contain a cycle, or name a task that was never added, should the method raise an error or return a partial path?
#### What This Part Should Cover
- An order that respects every dependency, produced without disturbing the scheduler's live state
- Detection and reporting of cycles and missing dependencies
- Time and space complexity in terms of tasks and dependencies
### What a Strong Answer Covers
- Settles the contracts of all four operations before coding, since they are left open
- A clear task state model shared by every operation
- Ready-task tracking that avoids rescanning finished tasks
- A dependency-respecting order with cycle detection
- Tests written for each part before moving on, including edge cases
- Pacing that leaves time to code the third part in a staged interview
### Follow-up Questions
- `getNextTask` must now return the earliest-added ready task. What changes, and at what cost?
- Several workers call `getNextTask` and `completeTask` concurrently. How do you keep the scheduler consistent?
- A task fails instead of completing. How should its dependents be handled?
- How would you return the groups of tasks that can run in parallel at each step, rather than a single path?
Overview: Brex technical screen: build an in-memory task scheduler in three stages, with operations to add tasks, hand out the next ready task, complete tasks and return a valid execution order. Tests class design, dependency tracking, optimizing a first version and writing your own tests as you go.