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

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.

Loading coding console...

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