Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

Jul 2026

Summary

Amazon SWE interview with a tricky inventory pricing problem. The algorithmic setup looked straightforward at first glance but the operation structure made it a lot more subtle than a typical range-compression question.

Questions Asked (1)

You have an array of product prices and two integers k and d. In one operation you pick two indices x and y, pick a value p between 1 and k, add p to prices[x] and subtract p from prices[y]. Find the minimum number of such operations to make the difference between the max and min price strictly less than d.

Algorithms & Data Structures

Author's notes

Spent a good chunk of time just staring at the operation definition.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and confirm that the total sum of prices remains constant. Then, recognize that the operation allows transferring up to k units between any two elements, and the goal is to minimize the number of transfers to reduce the range below d. The optimal strategy is to sort the array and use a sliding window to find the smallest number of elements to adjust, computing the required transfers based on the sum of excess above the target maximum.

Pro tip: Always discuss edge cases like when the initial range is already less than d (answer 0) or when k=0 (impossible), and mention that the problem can be solved in O(n log n) due to sorting, which is efficient for large inputs.

1. Understand the operation and invariants

Explain that each operation transfers up to k units from one element to another, preserving the total sum. The goal is to make max - min < d with minimum operations.

2. Sort and identify target window

Sort the prices. The optimal final configuration will have all elements within a window of size d. Use a sliding window to find the window that minimizes the number of operations needed to bring all elements into that window.

3. Compute required transfers

For a chosen window [L, L+d), elements below L need to be increased, and elements above L+d need to be decreased. The total amount to transfer is the sum of deficits (or excesses), and the number of operations is ceil(total_transfer / k).

4. Minimize over all windows

Iterate over all possible windows (using two pointers) and compute the minimum operations. Return the minimum.

5. Handle edge cases and complexity

Check if initial range < d (return 0). If k=0 and range >= d, return -1. Discuss time complexity O(n log n) and space O(1) or O(n) depending on implementation.

Key Points to Mention

The total sum of prices is invariant under the operation.
Each operation can reduce the range by at most 2k (by increasing the minimum and decreasing the maximum).
Sorting the array helps in efficiently finding the optimal window of size d.
The number of operations for a window is ceil(total_excess / k), where total_excess is the sum of amounts by which elements exceed the window's upper bound (or fall below the lower bound).
Sliding window technique allows checking all possible windows in O(n) after sorting.
Edge cases: already valid (0 operations), impossible (k=0 and range >= d), and large k (1 operation may suffice).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.