Solve Two OA Algorithm Problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The post describes two separate coding questions from an online assessment:
1. **Greedy deletion by minimum value**
Given an integer array `nums`, repeatedly perform the following operation until every element has been deleted:
- Among all undeleted elements, choose the one with the smallest value. If multiple elements have the same value, choose the leftmost one.
- Add its value to the answer.
- Delete that element and its immediate neighbors in the original array (`i - 1` and `i + 1`) if those neighbors have not already been deleted.
Return the final accumulated answer.
2. **Minimum emergency refill days**
You manage a warehouse with capacity `max_products` and initial inventory `0`. On day `i`, the inventory changes by `task[i]` at the end of the day. Before processing a day, you may perform an emergency refill and increase the inventory by any amount, as long as the inventory after the refill does not exceed `max_products`. Using a refill on a day counts as one refill day regardless of how much inventory you add.
Constraints:
- After each day, inventory must never exceed `max_products`.
- On days where `task[i] == 0`, the end-of-day inventory must be non-negative.
- On other days, negative inventory is temporarily allowed.
Return the minimum number of refill days needed to satisfy all constraints, or `-1` if no valid plan exists.
Quick Answer: These two problems evaluate proficiency with greedy algorithms, array manipulation, simulation of stateful processes, and feasibility analysis under capacity constraints.
Part 1: Greedy Deletion by Minimum Value
You are given an integer array nums. Repeatedly perform the following operation until every element has been deleted: choose the undeleted element with the smallest value; if several undeleted elements share that value, choose the leftmost one. Add its value to the answer, then delete that element and its immediate neighbors in the original array (index i - 1 and i + 1) if they have not already been deleted. Return the final accumulated answer.
Constraints
- 0 <= len(nums) <= 2 * 10^5
- -10^9 <= nums[i] <= 10^9
- Use 64-bit arithmetic in fixed-width languages because the sum can exceed 32-bit range.
Examples
Input: ([3, 1, 5, 2, 4],)
Expected Output: 3
Explanation: Pick 1 at index 1, deleting indices 0, 1, 2. Then pick 2 at index 3, deleting indices 3 and 4. Total = 1 + 2 = 3.
Input: ([1, 1, 1],)
Expected Output: 2
Explanation: Tie-breaking chooses the leftmost 1 first, deleting indices 0 and 1. The remaining 1 at index 2 is then chosen. Total = 2.
Hints
- The next chosen element depends only on value and original index, so consider processing elements in sorted order.
- Instead of physically removing items from the array, keep a boolean array that marks whether each index has already been deleted.
Part 2: Minimum Emergency Refill Days
A warehouse has capacity max_products and starts with inventory 0. On day i, the inventory changes by task[i] at the end of the day. Before a day starts, you may perform at most one emergency refill and increase the inventory by any amount, as long as the inventory immediately after the refill does not exceed max_products. Using a refill on a day counts as one refill day no matter how much you add. The rules are: inventory must never exceed max_products, either after a refill or after the day's change; on days where task[i] == 0, the end-of-day inventory must be non-negative; on days where task[i] != 0, negative end-of-day inventory is allowed. Return the minimum number of refill days needed, or -1 if no valid plan exists.
Constraints
- 0 <= len(task) <= 2 * 10^5
- 1 <= max_products <= 10^9
- -10^9 <= task[i] <= 10^9
- Use 64-bit arithmetic for prefix sums and bounds in fixed-width languages.
Examples
Input: (10, [-3, 0, -3, 0])
Expected Output: 1
Explanation: Refill once on the first zero day to the maximum safe level. That single refill keeps the later zero day non-negative as well.
Input: (5, [-1, 0, 5, -8, 0])
Expected Output: 2
Explanation: The +5 day limits how much inventory can safely be carried early, so one refill is needed at the first zero day and another at the last zero day.
Hints
- Let prefix[i] be the sum of task[0] through task[i]. If the total refill amount used so far is R, then the inventory after day i is R + prefix[i].
- When a zero-day forces more inventory, it is optimal to refill on that day and raise R to the largest value that is still safe for all remaining days.