Amazon·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Amazon SWE interview with a pretty meaty algorithmic problem. One question, but it had enough depth to chew on for a while.

Questions Asked (1)

You have k items with given sizes and n bins with given capacities. Process items left to right: for each item, place it in the leftmost bin that has enough remaining capacity, then reduce that bin's capacity accordingly. Items that can't be placed are left unplaced. Return the count of unplaced items. Design a solution that handles up to 2×10^5 total items and bins in O((n + k) log n) time. What data structure would you use?

Algorithms & Data StructuresSystem Design

Author's notes

My first instinct was a segment tree on the bins, storing the max remaining capacity in each subtree.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and confirm the required time complexity. Then, propose using a segment tree that stores the maximum remaining capacity in each segment, allowing efficient leftmost bin search via binary search on the tree. Finally, discuss the update operation and analyze the time complexity.

Pro tip: Mention that a Fenwick tree with binary lifting can also achieve O(log n) per operation, but a segment tree is more straightforward for finding the leftmost bin with sufficient capacity. Also, note that if capacities are small, a bucket approach might work, but it won't meet the worst-case time complexity.

1. Understand the problem and constraints

Restate the problem: process items in order, place each in the leftmost bin with enough capacity, and count unplaced items. Note that n and k can be up to 2×10^5, so an O(nk) solution is too slow.

2. Identify the need for efficient search and update

We need to quickly find the leftmost bin with remaining capacity ≥ item size, and then update that bin's capacity. This suggests a data structure that supports range queries and point updates.

3. Choose a segment tree storing maximum capacity

Use a segment tree where each node stores the maximum remaining capacity in its segment. To find the leftmost bin with capacity ≥ s, traverse the tree: at each node, check if the left child's max ≥ s; if so, go left; otherwise, go right.

4. Detail the algorithm and complexity

For each item, query the segment tree to find the leftmost bin. If found, update that bin's capacity (point update). Each operation takes O(log n), so total O((n+k) log n). If not found, increment unplaced count.

5. Discuss alternatives and edge cases

Mention that a Fenwick tree with binary lifting can also work, but segment tree is simpler. Handle edge cases: item larger than any bin, all bins full, etc.

Key Points to Mention

Segment tree storing maximum remaining capacity per segment
Leftmost search via recursive traversal: check left child first
Point update after placing an item
Time complexity: O((n + k) log n)
Space complexity: O(n)
Alternative: Fenwick tree with binary lifting (also O(log n) per operation)

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