Staged Task Scheduler: Dispatch Ready Tasks, Complete Them and Return an Execution Order

Quick 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.

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.

Brex logo
Brex
Nov 9, 2026
mediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals
0
0

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 Guidance

  • 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.

What This Part Should Cover Guidance

  • 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?

What This Part Should Cover Guidance

  • 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.

Clarifying Questions for this Part Guidance

  • 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 Guidance

  • 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 Guidance

  • 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 Guidance

  • 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?