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.

Solve Two OA Algorithm Problems | Amazon Coding Question

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.

Input: ([],)

Expected Output: 0

Explanation: There are no elements to delete, so the answer is 0.

Input: ([7],)

Expected Output: 7

Explanation: The single element is chosen and deleted, so the answer is 7.

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

Expected Output: 8

Explanation: Pick 1 at index 2 first, deleting indices 1, 2, 3. Then pick 2 at index 0, and finally 5 at index 4. Total = 1 + 2 + 5 = 8.

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.

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

Expected Output: 0

Explanation: There are no days with task[i] == 0, so negative inventory is allowed whenever it appears. No refill is required.

Input: (3, [-3, 0, 4, 0])

Expected Output: -1

Explanation: To make the first zero day non-negative you would need too much inventory, but any such choice would make the later +4 day exceed capacity.

Input: (7, [])

Expected Output: 0

Explanation: With no days to process, no refill is needed.

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.

Quick Overview

These two problems evaluate proficiency with greedy algorithms, array manipulation, simulation of stateful processes, and feasibility analysis under capacity constraints.