Prove reservoir sampling correctness

Q: Prove reservoir sampling correctness

This is a Coding & Algorithms interview question from Other for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design an algorithm to sample k items uniformly at random from a stream of unknown and potentially massive length N, using O(k) memory and one pass. (a) Write the algorithm for k=1 and generalize to k>1. (b) Prove by induction that after processing i items, each seen item has probability k/i to be in the reservoir. (c) Discuss time and memory complexity, and outline how you would adapt it for weighted sampling.

Prove reservoir sampling correctness

Comments (0)