Reservoir Sampling | Algorithm R | Interviewing Questions
Channel: Try and Catch Jeeves
Date: 2020-09-15

Hello World!

This is a video about reservoir sampling! I completely bombed an interview I gave on this topic and used it as an opportunity to learn as much as I can about the subject. 

Here are rough timestamps on this video to help you navigate to various sections (for example if you'd like to skip my mini-rant lol)

Outline: 
Introduction: 0:00  
Mini-Rant 2:20
Context: 4:11
Beginner's Mind & Guessing: 5:22
Code: 8:13
Intuition / Explanation: 11:05
Mathematical Proofs: 14:00

Here are some links you might want to peruse in your free time. 
Wiki: https://en.wikipedia.org/wiki/Reservoir_sampling
Original Paper: http://www.cs.umd.edu/~samir/498/vitter.pdf
Combinatorial Proof: https://people.orie.cornell.edu/snp32/orie_6125/algorithms/reservoir-sampling.html


Ask Questions and Stay Curious! Good luck with your interviews!
-Jeeves