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 Take-home Project rounds at Amazon.

What role is this question designed for?

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

Maximize optional tasks under daily limit

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You are given an integer limit and two integer arrays required and optional of length n. For each day i, you must schedule required[i]. If time remains on that day (not exceeding limit), you may schedule at most one optional task; each optional task can be used at most once and can be assigned to any day. Goal: maximize the number of optional tasks scheduled across n days without exceeding the daily limit. Return: ( 1) the maximum count of scheduled optional tasks, and ( 2) one valid assignment of optional tasks to days (or indicate none for a day). Example: limit = 7 required = [4, 5, 2, 4] optional = [5, 6, 3, 4] One optimal plan schedules 2 optional tasks. Answer the following: - Describe an efficient algorithm, prove why it is correct, and analyze time and space complexity. - Implement the algorithm in the language of your choice. - How would your approach change if each optional task were tied to a specific day (i.e., optional[i] can only be used on day i)? - How would you handle cases where some required[i] > limit? - How would you generalize if up to k optional tasks could be scheduled per day?

Quick Answer: This question evaluates algorithmic problem-solving in scheduling and combinatorial optimization, assessing understanding of capacity-constrained assignment, greedy or matching strategies, and correctness and complexity reasoning.

You are given an integer `limit` and two integer arrays `required` and `optional` of length `n`. For each day `i` you must schedule `required[i]`. If time remains on that day without exceeding `limit`, you may schedule **at most one** optional task. Each optional task can be used **at most once** and may be assigned to **any** day. Return a tuple `(count, assignment)`: 1. `count` — the maximum number of optional tasks that can be scheduled across all `n` days, and 2. `assignment` — a list of length `n` where `assignment[i]` is the **cost of the optional task** placed on day `i`, or `-1` if no optional task is placed on that day. Any one valid optimal assignment is accepted; this reference produces the deterministic plan that, processing days in ascending order of free slack, gives each day the cheapest still-unused optional task that fits. A day `i` has free slack `limit - required[i]`. An optional task of cost `o` fits on day `i` only if `o <= limit - required[i]` (so days where `required[i] >= limit` can hold no optional task). **Example** ``` limit = 7 required = [4, 5, 2, 4] optional = [5, 6, 3, 4] => (2, [3, -1, 4, -1]) ``` Day 0 (slack 3) takes optional 3; day 2 (slack 5) takes optional 4. Days 1 and 4 have no room for any remaining optional, so 2 optional tasks is optimal.

Constraints

1 <= n <= 10^5 (n may be 0 if both arrays are empty)
1 <= limit <= 10^9
0 <= required[i], optional[i] <= 10^9
len(required) == len(optional) == n
If required[i] >= limit, day i cannot hold any optional task

Examples

Input: (7, [4, 5, 2, 4], [5, 6, 3, 4])

Expected Output: (2, [3, -1, 4, -1])

Explanation: Prompt example. Slacks: day0=3, day1=2, day2=5, day3=3. Processing tightest-first, day1(2) fits nothing unused that helps, day0(3) takes optional 3, day3(3) finds no remaining fit, day2(5) takes optional 4. Max = 2.

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

Expected Output: (0, [-1, -1, -1])

Explanation: Every day's required equals limit, so slack is 0 everywhere and no optional task fits.

Input: (10, [1], [5])

Expected Output: (1, [5])

Explanation: Single day with slack 9; optional cost 5 fits, so it is scheduled.

Input: (5, [], [])

Expected Output: (0, [])

Explanation: Empty input: no days, no optional tasks, count 0 and empty assignment.

Input: (10, [2, 2], [8, 8])

Expected Output: (2, [8, 8])

Explanation: Both days have slack 8 and both optional tasks cost exactly 8, so both fit (<= boundary).

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

Expected Output: (1, [-1, 1])

Explanation: Day0 has required 5 > limit 3 (slack negative) so it holds nothing; day1 has slack 2 and takes the cheapest fitting optional, cost 1.

Input: (8, [3, 4, 6], [4, 4, 4])

Expected Output: (2, [4, 4, -1])

Explanation: Slacks: day0=5, day1=4, day2=2. Tightest-first: day2(2) fits no cost-4 task; day1(4) takes a 4; day0(5) takes a 4. Two optional tasks scheduled.

Hints

Each day independently offers `limit - required[i]` units of free slack; an optional task only fits if its cost is <= that slack. The day's required cost is fixed and unavoidable.
This reduces to a bipartite matching: optional task fits day iff cost <= slack. Because both sides are one-dimensional thresholds, sorting beats general matching.
Sort the day slacks ascending and the optional costs ascending. Walk the days from tightest to loosest and assign each the cheapest still-unused optional that fits — an exchange argument shows this never reduces the achievable count.
Follow-up — optional[i] tied to day i: it becomes n independent yes/no checks (`optional[i] <= limit - required[i]`); no sorting or matching needed.
Follow-up — required[i] > limit: that day is infeasible for its own required task; either report it as impossible or treat its optional slack as 0 (it can hold nothing). Follow-up — up to k optional per day: give each day k slots and run the same sorted-greedy, filling the smallest fitting optional tasks into the tightest available slots.

Quick Overview

This question evaluates algorithmic problem-solving in scheduling and combinatorial optimization, assessing understanding of capacity-constrained assignment, greedy or matching strategies, and correctness and complexity reasoning.