How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Scale AI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Scale AI during technical interviews.

Schedule Ready Tasks by Deadline | Scale AI Coding Question

Schedule Ready Tasks by Deadline

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

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

Part 1: Earliest Deadline Task Without Dependencies

You are given a list of tasks with no dependencies. Each task is represented as a pair `(task_id, deadline)`. Return the `task_id` of the task with the smallest deadline. If multiple tasks share the same smallest deadline, return the one with the smaller `task_id` for a consistent answer. If the input list is empty, return `None`.

Constraints

0 <= len(tasks) <= 100000
`task_id` values are unique integers
`deadline` is an integer in the range [-10^9, 10^9]

Examples

Input: [(101, 5), (102, 2), (103, 8)]

Expected Output: 102

Explanation: Task 102 has the smallest deadline: 2.

Input: [(3, 4), (1, 4), (2, 6)]

Expected Output: 1

Explanation: Tasks 3 and 1 tie on deadline 4, so return the smaller task_id: 1.

Input: [(7, 10)]

Expected Output: 7

Explanation: Only one task is present.

Input: []

Expected Output: None

Explanation: Empty input has no task to return.

Hints

A full sort is unnecessary; you only need to track the best task seen so far.
Decide how to handle ties before you start scanning.

Part 2: Schedule Ready Tasks by Deadline

Each task is represented as `(task_id, deadline, prerequisites)`, where `prerequisites` is a list of task IDs that must be completed first. The dependency graph is guaranteed to be a DAG. A task is ready when all its prerequisites have been completed. Starting with all ready tasks, repeatedly choose the ready task with the smallest deadline. If multiple ready tasks have the same deadline, choose the smaller `task_id`. Mark that task as completed, unlock any tasks whose prerequisites are now all done, and continue until all tasks are scheduled. Return the execution order as a list of task IDs. Use a simple ready-list approach that scans the current ready tasks each step.

Constraints

0 <= number of tasks <= 3000
0 <= total number of prerequisite references <= 20000
`task_id` values are unique integers
Every prerequisite ID appears in the task list
The dependency graph is a DAG

Examples

Input: [(1, 4, []), (2, 2, []), (3, 3, [1, 2]), (4, 1, [2])]

Expected Output: [2, 4, 1, 3]

Explanation: Start with ready tasks 1 and 2. Pick 2 first, which unlocks 4. Then pick 4, then 1, then 3.

Input: [(1, 2, []), (2, 2, []), (3, 1, [1]), (4, 5, [2])]

Expected Output: [1, 3, 2, 4]

Explanation: Tasks 1 and 2 tie initially, so choose 1 first. That unlocks task 3, which then has the smallest deadline.

Input: [(5, 7, []), (6, 1, [5]), (7, 2, [6])]

Expected Output: [5, 6, 7]

Explanation: This is a simple dependency chain.

Input: []

Expected Output: []

Explanation: No tasks means no execution order.

Hints

Track how many prerequisites each task still needs; this is often called an indegree count.
Keep a list of currently ready tasks, and linearly scan that list to find the next task to run.

Part 3: Optimized Deadline-Aware Task Scheduler

You are given tasks as `(task_id, deadline, prerequisites)`, and the dependency graph is a DAG. A task becomes ready once all prerequisite tasks have been completed. Repeatedly execute the ready task with the smallest deadline; if there is a tie, choose the smaller `task_id`. Unlike the previous version, you must optimize the selection of the next ready task by using an efficient data structure instead of scanning the full ready list each time. Return the full execution order.

Constraints

0 <= number of tasks <= 100000
0 <= total number of prerequisite references <= 200000
`task_id` values are unique integers
Every prerequisite ID appears in the task list
The dependency graph is a DAG

Examples

Input: [(1, 4, []), (2, 2, []), (3, 3, [1, 2]), (4, 1, [2])]

Expected Output: [2, 4, 1, 3]

Explanation: The heap always gives the smallest-deadline ready task.

Input: [(10, 5, []), (11, 1, []), (12, 3, [10]), (13, 2, [11]), (14, 4, [10, 11])]

Expected Output: [11, 13, 10, 12, 14]

Explanation: Task 11 runs first, unlocking 13. Task 10 later unlocks both 12 and 14.

Input: [(1, 1, []), (2, 1, []), (3, 1, [1, 2])]

Expected Output: [1, 2, 3]

Explanation: Tasks 1 and 2 tie initially, so use the smaller task_id first.

Input: []

Expected Output: []

Explanation: Empty input returns an empty schedule.

Input: [(9, 100, [])]

Expected Output: [9]

Explanation: A single task is immediately ready.

Hints

A min-heap is a natural way to repeatedly retrieve the smallest ready task.
You still need the same graph bookkeeping as before: indegrees and edges from each prerequisite to the tasks it unlocks.

Quick Overview

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.