Place items into earliest fitting bins

Q: Place items into earliest fitting bins

This question evaluates a candidate's ability to combine greedy online placement reasoning with efficient dynamic data-structure use to track and update bin capacities under streaming input.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Place items into earliest fitting bins

Overview

Comments (0)