Implement Stream Sampling with Distribution Verification
Last updated: September 4, 2025
Quick Overview
Implement reservoir sampling over a data stream and verify the sampled distribution matches the expected distribution using statistical tests.
Perplexity
September 4, 202515
9
2,573 solved
Implement reservoir sampling over a data stream and verify the sampled distribution matches the expected distribution using statistical tests.
Tests probabilistic reasoning and data structure design. Relevant to Perplexity's data sampling for model training and evaluation.
What the Interviewer Expects
- Implement reservoir sampling correctly
- Verify uniform sampling property
- Apply chi-squared test for distribution verification
- Handle edge cases with small streams
- Discuss the theoretical guarantee of reservoir sampling
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you extend this to weighted sampling?
- What if you need to sample from a distributed stream?
- How many samples do you need for statistical significance?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
The core challenge in this problem is implementing reservoir sampling, a technique that allows us to sample 'k' items from a stream of 'n' items uniformly without knowing 'n'. This is essential becaus...
Approach
- Reservoir Sampling: Initialize an array
reservoirof sizekto hold our sampled items. For the firstkitems, we fill the reservoir directly. For every subsequent item (fromk+1ton)...
Submit Your Answer
