Weighted Sampling Without Replacement
items is a list of [value, weight] pairs. weightedSample(items, k, random) returns k distinct values chosen so that each value's chance of inclusion follows its weight — heavier values are picked more often, and with k = 1 each value's probability is its weight over the total. Values with weight <= 0 are never chosen; return fewer than k when fewer are eligible.
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.
weightedSample([["a", 1], ["b", 2], ["c", 3], ["d", 4], ["z", 0]], 1, random) -> "d" about 40% of the time, "a" about 10%, "z" never
The harness runs your function thousands of times with a seeded generator and checks sizes, membership, single-draw frequencies, and that a lighter value is never picked more often than a heavier one — its result is "ok" or a message saying what was off.
Hints
Hint 1
Drawing one value at a time and removing it works but is fiddly. A-Res does it in one pass: give each item the key random()^(1/weight) and keep the k items with the largest keys.
Hint 2
Skip items with weight <= 0 before drawing their keys. A size-k min-heap keyed on the A-Res key makes it streaming.