Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Amazon SWE coding round, one question the whole time. Pretty standard binary search problem but the constraint about shipping order tripped me up for a minute.

Questions Asked (1)

Given an array of package weights and a number of days D, find the minimum ship capacity that allows all packages to be shipped within D days. Packages must be loaded in order, and on any given day you can load packages up to the capacity limit.

Algorithms & Data Structures

Author's notes

I knew binary search was involved pretty quickly, the tricky part was nailing down the bounds.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the minimum capacity lies between the maximum package weight and the sum of all weights. Use binary search on this range, and for each candidate capacity, simulate the shipping process to check if all packages can be shipped within D days. The first feasible capacity found is the minimum.

Pro tip: Clarify that packages must be shipped in the given order, and emphasize that the binary search reduces time complexity to O(n log(sum - max)). Mention that this is optimal because the feasibility check is monotonic: if a capacity works, any larger capacity also works.

1. Define search bounds

Set low to the maximum package weight (since a ship must carry at least the heaviest package) and high to the sum of all weights (one day shipping).

2. Binary search for capacity

While low < high, compute mid = low + (high - low) / 2 and check if mid is feasible.

3. Feasibility check

Simulate loading packages in order: accumulate weights until adding the next would exceed capacity, then increment day count and start a new day. If days needed <= D, capacity is feasible.

4. Adjust bounds

If feasible, set high = mid; else set low = mid + 1. Continue until low == high.

5. Return result

The minimum capacity is low (or high, since they are equal).

Key Points to Mention

Binary search on the answer space (capacity) rather than on the array.
Monotonicity of feasibility: if capacity C works, any C' > C also works.
Time complexity: O(n log(sum - max)) where n is number of packages.
Space complexity: O(1) extra space.
Edge cases: D >= n (capacity = max weight), D = 1 (capacity = sum), and handling large sums (use long if needed).
The simulation must preserve package order and cannot split a package.

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