Stratified Sampling with Largest-Remainder Allocation
items is a list of [value, stratum] pairs — think evaluation examples tagged by locale. stratifiedSample(items, n, random) returns n values whose strata keep the original proportions, chosen uniformly within each stratum, in any order.
Allocate n proportionally to stratum size using largest-remainder rounding: floor every exact share, then hand the leftover slots, one each, to the strata with the largest fractional parts, ties broken by stratum name ascending.
100 items: 50 "en", 30 "fr", 15 "de", 5 "ja"; n = 10 exact shares 5, 3, 1.5, 0.5 -> floors 5, 3, 1, 0 -> one slot left -> "de" (remainder .5, before "ja" by name) allocation: en 5, fr 3, de 2, ja 0
random is a function returning a uniform float in [0, 1). Use only it for randomness, so the harness can seed it and check your output statistically. The harness runs your function thousands of times and checks sizes, membership, each stratum's count, and per-item frequencies — its result is "ok" or a message saying what was off.
Hints
Hint 1
Group the values by stratum, compute each exact share size × n / total, and floor it.
Hint 2
The shortfall n − sum(floors) goes one slot each to the strata with the largest remainders (name ascending on ties). Then draw each stratum's allocation uniformly — a reservoir sample per stratum works.