Katkat
Back

Schedule Ready Tasks by Deadline

Scale AISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of task scheduling and dependency management in directed acyclic graphs, along with algorithmic selection and data-structure-based optimization for repeated minimum-deadline retrieval.

You are building a workflow scheduler.

Each task has:

  • a unique task_id
  • an integer deadline
  • an optional list of prerequisite tasks that must be completed before this task becomes ready

Assume the dependency graph is a DAG.

Implement the scheduler in three stages:

  1. Basic version: Given a list of tasks with no dependencies, return the task with the smallest deadline.
  2. Dependency-aware version: Tasks may have prerequisites. Repeatedly select the currently ready task with the smallest deadline, mark it as completed, and add any newly unlocked tasks to the ready set. Return a valid execution order.
  3. Optimized version: Improve the time complexity of selecting the next ready task by using an efficient data structure instead of scanning the full ready list each time. Analyze the time complexity.

If multiple ready tasks have the same deadline, you may break ties by task_id or return any consistent order.