Hey y’all, I’m sure everyone’s studies are going smoothly!

I’ve been seeing Leetcode 398 Random Pick Index being asked very, very often lately. The OG is never asked (or at least from what I’ve seen), so in its place, Meta asks two variants that involve the Reservoir Sampling technique:

1. What if you had to sample K random numbers in an array?
2. What if you had to sample one random index of the maximum value in an array?

Sounds trivial until you get to the laundry list of constraints, which among others, restricts you from using extra space complexity. Not only that, you must also do it in O(N) time complexity. Please don’t spend time generating random numbers in a while loop - Meta will reject it, sadly.
If you're interested in the mathematical proof of reservoir sampling and why it ensures equal probability, this is a pretty Good Explanation.

Check it out (or not!):

Reference to the OG LC problem: https://leetcode.com/problems/random-pick-index/description/

Good luck on your phone screens & onsite loops.