Randomized Sampling and Probability Distributions

Opening scenario

Random Pick with Weight (LC 528). You get an array w of positive integer weights. pickIndex() must return index i with probability w[i] / sum(w). Then the follow-up: Implement Rand10() Using Rand7() (LC 470). Build a uniform rand10() when your only random source is rand7().

LC numbers identify LeetCode problems.

Start small. Three items A, B and C must come back with probabilities 0.2, 0.3 and 0.5. Your only tool is random.random(), a uniform float in [0, 1). How do you turn one uniform number into this skewed choice? And how do you prove that the result is exact?

Interviewers use this problem family to check three skills:

1. Construct: turn a known source, usually a uniform one, into the target distribution.
2. Prove: show that each outcome has exactly the required probability.
3. Optimize: cut the time, the memory or the number of random calls per sample.

The proof step usually separates strong candidates from the rest.