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

IntermediatePrefer not to say

Apr 2026Remote

Summary

Amazon SWE online assessment with at least two algorithm problems in the same window. The main one was a ring-based redistribution problem with a directional constraint that trips you up if you approach it naively. Prep on the line version first or you'll probably get burned.

Questions Asked (1)

You have n warehouses arranged in a circle, each holding some number of products. Moving one product across a single edge costs 1, but all moves must flow in one fixed direction around the ring (no mixing clockwise and counterclockwise). Given that the total is divisible by n, find the minimum cost to equalize all positions.

Algorithms & Data Structures

Author's notes

The directional constraint is what makes this hard.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, recognize that the target amount per warehouse is the average. Then, compute the net surplus or deficit at each position and use prefix sums to determine the cumulative flow across each edge. The minimum cost is the sum of the absolute values of these cumulative flows, but since all moves must be in one direction, we need to adjust by subtracting the median of the prefix sums to minimize the total cost.

Pro tip: Clarify that the one-direction constraint means we cannot simply take the sum of absolute prefix sums; instead, we must shift all flows by a constant (the median) to ensure non-negativity. This is a key nuance that many candidates miss.

1. Compute the target

Calculate the average number of products per warehouse, which is the total divided by n. This is the goal for each position.

2. Calculate net surplus/deficit

For each warehouse, compute the difference between its current amount and the target. Positive means surplus, negative means deficit.

3. Compute prefix sums

Traverse the circle in the fixed direction and compute the cumulative sum of surpluses/deficits. These prefix sums represent the net flow that must cross each edge if we only move in that direction.

4. Adjust for one-direction constraint

Since all moves must be in one direction, the flows cannot be negative. Find the median of the prefix sums and subtract it from each prefix sum to get the actual non-negative flows.

5. Sum absolute flows

The minimum cost is the sum of the absolute values of the adjusted prefix sums. This gives the total number of product moves needed.

Key Points to Mention

The problem is a variant of the classic 'load balancing on a ring' or 'circular candy distribution' problem.
The one-direction constraint means we cannot independently choose the direction for each edge; all flows must be consistent.
Prefix sums represent the net flow across each edge before adjustment.
The median minimizes the sum of absolute deviations, which is why we subtract the median to enforce non-negativity.
Time complexity is O(n) after computing prefix sums, and space complexity is O(n) or O(1) if optimized.
Edge cases: all warehouses already equal (cost 0), n=1 (cost 0), and large values requiring 64-bit integers.

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