Katkat
Back

Maximize Throughput Packing Reserved Compute Slots With Limited Stock

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Choose how many reserved instances of each type to allocate into a shared rack-slot budget, each instance occupying exactly one slot, to maximize total throughput score given limited stock per type.

A cluster scheduler is handing out reserved compute slots for the next hour. There are n instance types; every reserved unit of type i, regardless of type, occupies exactly one slot, contributes a throughput score of scores[i], and only stock[i] units of that type exist. Decide how many units of each type to reserve so the total slots used don't exceed the budget and total throughput is maximized.

Function Signature

def max_total_score(scores: list[int], stock: list[int], slot_budget: int) -> int:

Rules

  • Choose integers x[i] with 0 <= x[i] <= stock[i] such that sum(x[i]) <= slot_budget.
  • Maximize sum(x[i] * scores[i]). Return that maximum; 0 if nothing can or should be reserved.

Constraints

  • 1 <= len(scores) == len(stock) <= 10^5
  • 0 <= scores[i] <= 10^6
  • 1 <= stock[i] <= 10^9
  • 0 <= slot_budget <= 10^9
  • sum(stock) can reach 10^14 and the answer can reach roughly 10^15 — both overflow a 32-bit integer, so use 64-bit arithmetic in languages with fixed-width ints. Both stay comfortably under 2^53, so plain Python ints or IEEE doubles used only for comparisons are fine.

Examples

scores = [50, 90, 20], stock = [3, 2, 100], slot_budget = 5
-> 330

Take both units of the 90-score type (180) and 3 of the 50-score type (150): 180 + 150 = 330, using all 5 slots. The 20-score type isn't needed.

scores = [12, 0, 7], stock = [1, 3, 999999999], slot_budget = 1000000000
-> 7000000005

Take the single 12-score unit, then as many of the 7-score units as exist (999,999,999 of them): 12 + 7 * 999999999 = 7000000005. The 0-score type adds nothing even though slots remain unused — there's no benefit and no penalty to leaving the budget partly empty.

Hints

Hint 1

Every unit weighs exactly 1 slot — ask whether that turns this into a much simpler problem than general bounded knapsack.

Hint 2

If you could only pick whole item types in some order and take as many of the best type as fit, would that ever be beaten by holding some of it back for a worse type?

Hint 3

Sort types by score descending and greedily fill the budget. Prove to yourself with an exchange argument why swapping any unit of a lower-score type for an available unit of a higher-score type never makes the total worse.

Hint 4

Watch the arithmetic: the running total and the budget itself both need 64-bit range, not just the per-type contribution.

Follow-up questions

  • What changes if each instance type can occupy a different number of slots (true bounded knapsack)? Why doesn't the greedy approach generalize?
  • How would you answer this online, where new instance types with their own stock keep arriving and you need the running-best allocation after each arrival?
  • If reserving a unit of a type also has a minimum-batch requirement (you must take 0 or at least k units of that type), how does the algorithm change?
  • How would you parallelize or stream this if n is 10^8 and the (scores, stock) pairs don't fit in memory at once?