Probability & Statistics
3 problems
Probability problems may require expected value computation, random sampling, or reservoir sampling. Key concepts: linearity of expectation, conditional probability, and geometric distribution. Reservoir sampling picks k items from a stream of unknown length in O(n) time and O(k) space.