C++ using reservoir sampling with explanation

  • 3

    The pseudocode of reservoir sampling with pool size 1 is:

    for ith element in stream
        t <- random()
        if(t%i==0)  // each element is selected with a probability of 1/i
            res <- ith element

    We need to proof the each element has a probability of 1/N to be selected where N is the length of stream.

    1. N = 1. Only one element in the stream, the probability is 1;
    2. N = 2. Obviously, probabilities of each element to be selected are 1/2;
    3. N = n. Suppose the probabilities of each element to be selected are 1/n, considering N = n + 1. For (n+1)th element, the probability that (n+1)th is selected is 1/(n+1). For 1,2,3..n elements, the probability is (1-1/(n+1))*(1/n)=1(n+1). Therefore, for N = n+1, the assumption maintains.

    Accepted Code:

    class Solution {
        ListNode* u;
        Solution(ListNode* head) {
            u = head;
        int getRandom() {
            int res, len = 1;
            ListNode* v = u;
                if(rand() % len == 0){
                    res = v->val;
                v = v->next;
            return res;

  • 0

    @birdxue Thanks for your explanation.
    You have a typo in equation 1(n+1) => 1/(n+1)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.