Reservoir Sampling Stream

Implement reservoir_sample(stream, k, seed), which draws a uniform random sample of k items from a stream of unknown length. Use O(k) memory, touch each item exactly once, make no second pass, and do not assume the length in advance. This is reservoir sampling. Use Algorithm R, exactly as prescribed (the tests check the byte-exact result, which every correct implementation of this spec produces):

1. Create the generator once: rng = random.Random(seed).
2. Iterate the stream with 0-based index i. For the first k items (i < k), append the item to the reservoir. No random draws are made for these items.
3. For each later item (i >= k), draw j = rng.randrange(i + 1); if j < k, replace reservoir[j] with the item. One draw per item, in stream order, and no other calls to the generator.
4. Return the reservoir list in its final slot order (do not sort it).

stream is an arbitrary iterable and may be a one-shot generator: iterate it once and never materialise it.

A research pipeline reading a tick stream of unknown length (forty million trades, or four hundred) works under this constraint.

Examples

reservoir_sample(range(10), 3, 42)
# [4, 1, 9]

reservoir_sample(["AAPL", "MSFT", "NVDA", "AMZN", "GOOG", "META", "TSLA"], 2, 7)
# ['TSLA', 'AMZN']

Constraints

• k >= 1. If the stream has at most k items, the reservoir is simply every item in stream order.
• Up to \(2 \times 10^5\) items in the hidden performance test, delivered by a generator expression: a solution that calls len(stream), converts to a list, or iterates twice will crash or fail it.
• Every item type must be preserved as-is (the sample is of the items, not of copies or keys).