Python data engineering interview problem. Difficulty: advanced. Pattern: Streaming. About 20 minutes. Part of the Pro drill bank.
Pick k items uniformly at random from a stream of unknown length, in one pass and O(k) memory. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.
Implement reservoir_sample(stream, k: int, seed: int) -> list. stream is an iterable you can loop over once, and its length is not known in advance (it may be a generator). Return a list of k items chosen uniformly at random from it: every item must have the same chance, k / n, of being in the result. If the stream has fewer than k items, return all of them in stream order. Use random.Random(seed) for all random choices so the result is repeatable for the same seed. Do not store the whole stream.
Input: sum(0 in reservoir_sample(iter(range(10)), 3, seed) for seed in range(1000)) < 400 Output: True A fair sample of 3 out of 10 contains item 0 in about 3 of every 10 runs (roughly 300 of 1000), well under 400.
Topics: lakebench, python, sampling, stream, random.
More Python interview questions · All interview problems · Learn data engineering
Interview-style drill: Pick k items uniformly at random from a stream of unknown length, in one pass and O(k) memory.
Implement `reservoir_sample(stream, k: int, seed: int) -> list`. `stream` is an iterable you can loop over **once**, and its length is not known in advance (it may be a generator). Return a list of `k` items chosen uniformly at random from it: every item must have the same chance, k / n, of being in the result. If the stream has fewer than `k` items, return all of them in stream order. Use `random.Random(seed)` for all random choices so the result is repeatable for the same seed. Do not store the whole stream.