Katkat
Back

Implement a Dependency-Aware Task Scheduler

Scale AISoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skills in dependency management, deadline-driven scheduling and algorithmic data-structure design, focusing on handling directed acyclic graphs and ordering constraints.

Implement a TaskManager class with two methods:

  • AddTasks(tasks): add one or more tasks into the system.
  • ConsumeTask(): return and remove the executable task with the earliest deadline.

Each task has the following fields:

  • id: unique task identifier
  • ddl: integer deadline, where a smaller value means an earlier deadline
  • subTasks: a list of prerequisite task IDs that must be completed before this task can be consumed

Requirements:

  1. Support multiple calls to AddTasks.
  2. ConsumeTask() should return the pending task with the smallest deadline among all currently executable tasks.
  3. A task is executable only if all of its prerequisite tasks have already been consumed.
  4. If no executable task exists, return NO_TASK.
  5. For this coding problem, assume task IDs are unique and the dependency graph is valid and acyclic.

Explain the data structures you would use and implement both methods efficiently.