179 questions
No questions match those filters.
How do you maintain a fixed-size, uniformly random samp...
This is one of the questions in the full AI/ML interview bank. Pro unlocks all 1789 questions; Premium includes the same bank plus the highest daily Practice limit.
See plansThe instinct to buffer a window and call a dataframe sampling function fails outright: the stream is unbounded, so buffering “the last hour” either blows memory once volume grows or silently drops representative coverage of older data. Fixed-stride sampling (keep every Nth item) is worse in a subtler way — it introduces periodicity bias if the stream has any structure at that interval, and a fixed sampling probability gives you a variable-size sample rather than a fixed k. Both approaches also assume you can compute a sampling probability from N, the total stream length, which is unknowable while the stream is still running.
Reservoir sampling is built for exactly this constraint. Initialize a buffer of size k with the first k items unconditionally. For every item that arrives after that, at position n, generate a random integer j in [0, n). If j < k, replace the item currently at index j in the buffer with the new one; otherwise discard the new item entirely. That’s the whole algorithm — one pass, one buffer, no lookahead.
The guarantee this produces is exact, not approximate: at any snapshot in the stream’s history, every item that has been seen so far has probability exactly k/n of currently occupying a slot in the buffer. Memory usage never grows past O(k) regardless of stream length, which is the property that makes it usable for maintaining a live, unbiased training buffer off a firehose that never stops — a fraud stream, a clickstream, or any feed where you need a representative sample without the option of ever seeing the whole dataset at once.