The task is to write a function which at any give point would return random character with equal proability of any character being read from infinite stream. You are reading stream one character at the time and cannot go back as soon as you move to the next character and have to select character at random with equal proability of any character being selected.
You cannot create an extra copy of the stream, i.e. have to do this in O(1) space.
Solution:
The algorithm is very simple but as usually with probability questions is counterintuitive. The idea is as you read new character you need either keep it as your random selection or skip it and repeat it for the next character in the stream but with lower probability.
So,
Step N=1, Keep character X1 with Propability P(1/N) = P(1/1) = P(1)
Step N=2, Keep character X2 with Probability P(1/N) = P(1/2)
Step N=3, Keep character X3 with Probability P(1/N) = P(1/3)
...
Step N=N, Keep character Xn with Probability P(1/N)
Here is sample solution in C#
static int randStream(int Max)
{
Random Rnd=new Random();
int sum = 0;
for (int i = 0;i < Max;i++)
{
if (i == 0) sum = i;
else
if (Rnd.Next(i) == 0) sum = i;
}
return sum;
}
Answers