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

Intermediate

Apr 2026

Summary

Amazon OA for a SWE role, one algorithmic problem about price normalization. Pretty standard online assessment format, nothing too surprising except the problem had some edge cases I didn't fully think through at first.

Questions Asked (1)

Given an array of product prices, a max step size k, and a target gap d, find the minimum number of operations to make the difference between the max and min price strictly less than d. Each operation lets you pick two products and shift value p (1 <= p <= k) from one to the other.

Algorithms & Data StructuresPricing & Monetization

Author's notes

My first instinct was greedy, just keep pulling the extremes toward each other.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the total sum of prices is invariant, so the goal is to redistribute values to minimize the range. Use binary search on the answer (number of operations) and check feasibility by determining if we can achieve max-min < d within that many operations, considering the max step size k per operation.

Pro tip: Clarify with the interviewer whether an operation can involve the same product twice or if it must be two distinct products; this edge case can affect the solution. Also, mention that the problem is equivalent to minimizing the number of transfers to make all values lie within a window of size d.

1. Understand the problem and invariants

Restate the problem: we can move up to k units from one product to another per operation. The total sum is fixed. The goal is to make max - min < d with minimum operations.

2. Binary search on the number of operations

Since the minimum operations is monotonic (if we can do it in x operations, we can do it in more), binary search over the answer. For a given mid, check if it's possible to achieve the goal within mid operations.

3. Feasibility check for a given operation count

For a fixed number of operations T, determine if we can adjust the array so that all values fall within some interval [L, L+d-1] (or (L, L+d)) while moving at most T*k total units (since each operation moves at most k). Also consider that each operation can only move between two products, but total moved units is the key constraint.

4. Compute minimum total movement needed

For a candidate interval [L, R] with R-L < d, compute the minimum total amount that must be moved to bring all values into this interval. This is the sum of excess above R and deficit below L, which must be equal due to sum conservation. The minimum total movement is the sum of excesses (or deficits).

5. Relate total movement to operations

Given total movement M, the minimum number of operations required is ceil(M / k) because each operation can move at most k units. However, if an operation must involve two distinct products, we might need at least 2 operations if M>0? Actually, if M>0, we need at least 1 operation, but ceil(M/k) already gives at least 1. So the condition is ceil(M/k) <= T.

Key Points to Mention

Sum invariance: total sum of prices remains constant.
Binary search on answer: monotonic property of feasibility.
Feasibility check: for a given number of operations, check if we can achieve max-min < d.
Total movement: compute minimum total amount to move to fit all values into a window of size d.
Operations vs movement: each operation moves at most k units, so number of operations >= ceil(total movement / k).
Edge cases: when d is very large (already satisfied), when k is large, and when array length is 1.

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