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

What role is this question designed for?

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

Select maximum tasks before deadlines | Amazon Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Select maximum tasks before deadlines states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Select maximum tasks before deadlines

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a set of tasks, each with a positive duration and a deadline (lastDay). You may schedule tasks in any order but only one at a time. Find the maximum number of tasks you can complete such that each chosen task finishes by its deadline. Return the count and describe an O(n log n) algorithm and its correctness intuition.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Select maximum tasks before deadlines states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a list of `tasks`, where each task is a pair `[duration, lastDay]`: `duration` is the positive number of time units the task takes, and `lastDay` is the deadline by which the task must be finished (the task must complete at or before this absolute time). You process tasks sequentially on a single machine starting at time 0 — only one task runs at a time, and you may schedule the chosen tasks in any order. A task counts as completed only if its finish time is `<= lastDay`. Return the maximum number of tasks you can complete on time. Describe an O(n log n) algorithm. Hint: sort by deadline and use a max-heap to greedily evict the longest task whenever the running schedule overruns the current deadline.

Constraints

1 <= tasks.length <= 10^4 (the list may also be empty, in which case the answer is 0)
tasks[i].length == 2
1 <= duration <= 10^4
1 <= lastDay <= 10^9
Time starts at 0; a chosen task with cumulative finish time t is valid only if t <= lastDay

Examples

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

Expected Output: 3

Explanation: Take durations 100, 200, 1000 (skip 2000). Finishing in deadline order: 100 (<=200), 300 (<=1250 for the 1000-task? compute via greedy) — the greedy keeps 3 tasks; the 2000-duration task is evicted as the longest when the schedule overruns.

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

Expected Output: 3

Explanation: All three fit: cumulative finish times 1<=2, 3<=4, 6<=6.

Input: [[5, 5], [4, 6], [2, 6]]

Expected Output: 2

Explanation: Take the 5-task (finish 5<=5). Adding the 4-task overruns deadline 6 (total 9), so evict the longest (the 5-task). Then the 2-task fits (4+2=6<=6). Two tasks remain.

Input: []

Expected Output: 0

Explanation: No tasks to schedule.

Input: [[10, 5]]

Expected Output: 0

Explanation: A single task of duration 10 cannot finish by deadline 5, so it is evicted; nothing can be completed.

Input: [[3, 3]]

Expected Output: 1

Explanation: The lone task finishes exactly at its deadline (3<=3).

Input: [[7, 7], [3, 5], [3, 5], [10, 30]]

Expected Output: 2

Explanation: Sorted by deadline: the two 3-tasks (deadline 5) conflict — only one fits. The 7-task overruns deadline 7 and is evicted. The 10-task fits comfortably. Two tasks complete.

Input: [[1, 1], [1, 1], [1, 1]]

Expected Output: 1

Explanation: All share deadline 1 and duration 1; only the first can finish by time 1, the rest would push the finish time past the deadline.

Hints

Process candidate tasks in non-decreasing order of deadline. Intuitively, to keep more tasks you should respect the earliest deadlines first.
Keep a running sum of durations of the tasks you have committed to. When that sum exceeds the current task's deadline, you have over-committed and must drop exactly one task.
Drop the task with the largest duration committed so far (a max-heap gives it in O(log n)). Removing the longest one frees the most time while keeping the count change neutral — you replace it with the shorter current task only if that helps.
Correctness intuition: sorting by deadline means every task still in the heap fits under all later deadlines too; evicting the longest keeps the chosen set both feasible and maximal in count at each step (an exchange argument).

Quick Overview