C++ using reservoir sampling with explanation


  • 3
    B

    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.
    Proof:

    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 {
    public:
    
        ListNode* u;
        Solution(ListNode* head) {
            u = head;
        }
        
        int getRandom() {
            int res, len = 1;
            ListNode* v = u;
            while(v){
                if(rand() % len == 0){
                    res = v->val;
                }
                len++;
                v = v->next;
            }
            return res;
        }
    };
    

  • 0
    H

    @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.