Katkat
Back

Load a Delivery Van With Equal-Size Crates for Maximum Profit

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Pick crates from limited stock to fill a van whose slots can number in the billions, when every crate takes one slot; recognize that the scary-looking bounded knapsack collapses to a greedy, then answer many capacity queries fast.

A wholesaler is loading a delivery van. The van has slots positions, and every crate occupies exactly one slot regardless of product. There are n products; product i earns profits[i] per crate and the warehouse has stock[i] crates of it. Profits may be zero or negative (clearance items that cost money to ship) - you never have to load them.

Part 1

def best_load(profits: list[int], stock: list[int], slots: int) -> int:

Return the maximum total profit. The van does not have to be full.

best_load(profits=[8, 3, 12, 5], stock=[3, 10, 1, 2], slots=5)  -> 41
# 1 crate x 12 + 3 crates x 8 + 1 crate x 5

best_load(profits=[2, 9], stock=[4, 1], slots=20)  -> 17
# only 5 crates exist; load all of them

best_load(profits=[7, 1], stock=[10**9, 10**9], slots=10**9)  -> 7000000000

Part 2

The dispatcher now asks about many vans against the same catalogue. Implement:

class LoadPlanner:
    def __init__(self, profits: list[int], stock: list[int]): ...
    def query(self, slots: int) -> int: ...

planner = LoadPlanner([8, 3, 12, 5], [3, 10, 1, 2])
[planner.query(c) for c in [0, 1, 4, 5, 7, 100]]  -> [0, 12, 36, 41, 49, 76]

Constraints

  • 1 <= n <= 10^5, -10^6 <= profits[i] <= 10^6, 1 <= stock[i] <= 10^9
  • 0 <= slots <= 10^9; up to 10^5 queries in Part 2.
  • Totals can exceed 2^31 (use 64-bit integers in fixed-width languages; Python is fine).
  • A classic DP over capacity is far too slow and too large here - explain why your approach is still optimal.

Hints

Hint 1

Every crate costs the same amount of capacity. What does that do to the usual knapsack trade-off between weight and value?

Hint 2

An exchange argument: if an optimal load contains a cheaper crate while a more profitable crate is left behind, swap them.

Hint 3

Sort products by profit descending and take as many as possible from each until slots run out; skip non-positive profits.

Hint 4

For many queries, precompute prefix sums of counts and of value over the sorted order, then binary-search the capacity.

Follow-up questions

  • Crates now come in two sizes (1 slot and 2 slots). Is greedy still optimal? What would you do?
  • Some products must be loaded together in fixed ratios (e.g., one lid per two jars). How does the model change?
  • How would you solve Part 1 in O(n) time without full sorting?
  • Stock levels change frequently between queries. Which data structure supports updates and capacity queries in logarithmic time?