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.