Select a random number from stream, with O(1) space | GeeksforGeeks

Given a stream of numbers, generate a random number from the stream. You are allowed to use only O(1) space and the input is in the form of stream, so can’t store the previously seen numbers.

This problem is a variation of Reservoir Sampling.

1) Initialize 'count' as 0, 'count' is used to store count of numbers seen so far in stream.
2) For each number 'x' from stream, do following
…..a) Increment 'count' by 1.
…..b) If count is 1, set result as x, and return result.
…..c) Generate a random number from 0 to 'count-1′. Let the generated random number be i.
…..d) If i is equal to 'count – 1′, update the result as x.

int selectRandom(int x)

{

    static int res;    // The resultant random number

    static int count = 0;  //Count of numbers visited so far in stream

    count++;  // increment count of numbers seen so far

    // If this is the first element from stream, return it

    if (count == 1)

        res = x;

    else

    {

        // Generate a random number from 0 to count - 1

        int i = rand() % count;

        // Replace the prev random number with new number with 1/count probability

        if (i == count - 1)

            res  = x;

    }

    return res;

}

    for (int i = 0; i < n; ++i)

        printf("Random number from first %d numbers is %d \n",

                                i+1, selectRandom(stream[i]));

To simplify proof, let us first consider the last element, the last element replaces the previously stored result with 1/n probability. So probability of getting last element as result is 1/n.

Let us now talk about second last element. When second last element processed first time, the probability that it replaced the previous result is 1/(n-1). The probability that previous result stays when nth item is considered is (n-1)/n. So probability that the second last element is picked in last iteration is [1/(n-1)] * [(n-1)/n] which is 1/n.

Read full article from Select a random number from stream, with O(1) space | GeeksforGeeks