# C++ using reservoir sampling with explanation

• 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;
}

int getRandom() {
int res, len = 1;
ListNode* v = u;
while(v){
if(rand() % len == 0){
res = v->val;
}
len++;
v = v->next;
}
return res;
}
};
``````

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

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