Senior LevelData Structures & Algorithms
What is Reservoir Sampling and how does it select K items uniformly from a stream?
ā Interview Prompt: Explain Reservoir Sampling algorithm, probability proof of uniform selection, O(N) time O(K) space, and streaming data applications.
Reservoir Sampling selects $K$ items uniformly at random from a stream of $N$ items where $N$ is unknown, using $O(K)$ memory.
Algorithm (Algorithm R by Vitter):
1
Fill reservoir with first $K$ items.
2
For each subsequent item $i$ (i > K):
ā¢
Generate random $j$ in $[1, i]$.
ā¢
If $j \leq K$: replace reservoir$[j-1]$ with item $i$.
Proof of Uniformity:
Probability that any item $i$ is in the final reservoir = $\frac{K}{N}$ (proved by induction).
Code Implementation Example
typescript
function reservoirSample<T>(stream: T[], k: number): T[] {
const reservoir = stream.slice(0, k); // fill with first k items
for (let i = k; i < stream.length; i++) {
const j = Math.floor(Math.random() * (i + 1)); // random index in [0, i]
if (j < k) {
reservoir[j] = stream[i]; // replace with probability k/(i+1)
}
}
return reservoir;
}
// Example: pick 3 random elements from a large stream
const sample = reservoirSample([1,2,3,4,5,6,7,8,9,10], 3);
console.log(sample); // 3 uniformly random elementsš”Reservoir Sampling ā O(N) time, O(K) space uniform random sampling from a stream.
šÆ Interview Key Takeaway
Reservoir Sampling is the standard algorithm for uniform random sampling from a data stream of unknown size. Used in analytics, A/B testing, and online ML.
#DSA#Reservoir Sampling#Randomised Algorithms#Streaming#Senior
Back to all Data Structures & Algorithms Questionsā