Reservoir Sampling Stream

A research pipeline is consuming a tick stream of unknown length: maybe forty million trades, maybe four hundred. You want a uniform random sample of k items, using O(k) memory, touching each item exactly once, with no second pass and no knowledge of the stream's length in advance. This is reservoir sampling, and the streaming constraint is exactly the one a desk's data infrastructure lives under.

Implement reservoir_sample(stream, k, seed) using 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.

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).