Reservoir Sampling
Sample k items uniformly without replacement from a stream of unknown length, in one pass and O(k) memory: reservoirSample(items, k, random). Return fewer than k items when the stream is shorter than k.
random is a function returning a uniform float in [0, 1). Use only it for randomness (derive integers as floor(random() * m)), so the harness can seed it and check your output statistically.
reservoirSample([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3, random) -> e.g. [7, 2, 9]
The harness runs your function thousands of times with a seeded generator and checks sizes, membership, and that every item is chosen with probability k / n within a tolerance — its result is "ok" or a message saying what was off.
Hints
Hint 1
Keep the first k items. For item i (0-based, i ≥ k), draw j uniformly in [0, i] and replace slot j when j < k.
Hint 2
Every item ends with probability k/n — prove it by induction if asked: item i is kept with probability k/(i+1), and each resident survives that step with probability i/(i+1).