How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Place items into earliest fitting bins

Quick Overview

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.

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.

Input: ([1, 1, 1, 1], [2, 2])

Expected Output: 0

Explanation: First two 1s fill bin0 to 0, next two fill bin1; all placed.

Input: ([3, 3, 3], [3, 3])

Expected Output: 1

Explanation: Two 3s fill both bins exactly; the third has nowhere to go -> 1 unplaced.

Input: ([], [5, 5])

Expected Output: 0

Explanation: No items to place.

Input: ([10], [])

Expected Output: 1

Explanation: No bins exist; every item is unplaced.

Input: ([4, 4], [10])

Expected Output: 0

Explanation: Both 4s fit in the single bin (10 -> 6 -> 2).

Input: ([6, 1, 6, 1], [7, 7])

Expected Output: 0

Explanation: 6->bin0([1,7]); 1->bin0([0,7]) (leftmost preference); 6->bin1([0,1]); 1->bin1([0,0]).

Input: ([5, 4, 3, 2, 1], [5, 4, 3])

Expected Output: 2

Explanation: 5->bin0, 4->bin1, 3->bin2 (all empty now); 2 and 1 cannot be placed -> 2 unplaced.

Input: ([8, 2, 2], [9, 1])

Expected Output: 2

Explanation: 8->bin0([1,1]); the two 2s have no bin with >=2 remaining -> 2 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.

Quick Overview