Place items into earliest fitting bins
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given k items with sizes items[0..k-1] and n bins with initial capacities caps[0..n-1]. Process items in order; for each size x, place it into the leftmost bin whose remaining capacity is at least x, then reduce that bin’s remaining capacity by x. If no such bin exists, the item remains unplaced. Return the number of unplaced items. Design an algorithm that supports up to 2×10^5 items and bins in total with O((n + k) log n) time, describing the data structure you would use.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Place items into earliest fitting bins states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given `k` items with sizes `items[0..k-1]` and `n` bins with initial capacities `caps[0..n-1]`. Process the items in order. For each size `x`, place it into the **leftmost** bin whose remaining capacity is at least `x`, then reduce that bin's remaining capacity by `x`. If no such bin exists, the item remains unplaced. Return the number of unplaced items.
Design an algorithm that supports up to 2*10^5 items and bins in total in O((n + k) log n) time. A max segment tree over bin capacities lets you binary-search down the tree for the leftmost bin whose remaining capacity is >= x (descend left whenever the left child's max >= x), then point-update that leaf and pull the maxima back up — each placement is O(log n).
Constraints
- 1 <= n + k <= 2*10^5
- 0 <= items[i], caps[j]
- Items must be processed strictly in the given order.
- Each item goes into the leftmost (smallest index) bin with remaining capacity >= its size.
Examples
Input: ([2, 3, 5], [4, 6, 2])
Expected Output: 1
Explanation: 2->bin0([2,6,2]); 3->bin1([2,3,2]); 5-> no bin has >=5 left, so 1 unplaced.
Input: ([5, 5, 5], [4, 4, 4])
Expected Output: 3
Explanation: No bin can hold a size-5 item, so all 3 items are unplaced.
Hints
- A linear scan per item is O(n*k) — too slow at 2*10^5. You need to find the leftmost bin with capacity >= x in O(log n).
- Build a max segment tree over the bins' remaining capacities. The root holds the maximum remaining capacity; if it is < x, the item is unplaceable.
- To find the leftmost fitting bin, descend from the root: go to the left child whenever its subtree max >= x, otherwise go right. This lands on the smallest index whose remaining capacity >= x.
- After placing, subtract x at that leaf and recompute maxima on the path back to the root — O(log n) per placement.