Impossible?

Puzzle:

This one is (supposedly) from a job interview for Google:

You’re being streamed an array of numbers. Every second you receive the next cell in the array. The array is finite but you don’t know when it ends or what’s it total length. Your job is to randomly pick one of the numbers from the array so that every number has the same probability of being selected i.e. if the array happens to be 10 cells long, each cell will have a probability of exactly 1/10 of being selected.

The catch is that you cannot locally save the array since that might take too much space. How do you do it?

(Courtesy of NewOrder Computer Security and Network Portal)

Potential Solution:

In probability and statistics there are two types of Uniform distribution, discrete and continuous. The above problem is an example of discrete, defined when – in a sequence of variables, a random variable has any of n possible values that are equally probable.

A popular example of discrete uniform distribution is known as the German tank problem. During World War II Allied intelligence used statistical methods to accurately predict production of German tanks using samples of data (ranges of variables over time which formed discrete uniform distribution).

To solve the above problem, the following sample C# code implements a simple algorithm:

First, we create a fraction class. (This is not absolutely necessary but will come in useful later.)

C#:

public class Fraction
    {
        public int numerator;
        public int denominator;

        public Fraction(string F)
        {
            numerator = Convert.ToInt32(F.Split('/')[0]);
            denominator = Convert.ToInt32(F.Split('/')[1]);
        }

        public static Fraction operator +(Fraction F1, Fraction F2)
        {
            int CD = F1.denominator*F2.denominator; //To find common denominator.

            F1.numerator *= CD/F1.denominator;
            F2.numerator *= CD/F2.denominator;

            return new Fraction((F1.numerator + F2.numerator).ToString() + '/' + CD.ToString());
        }

        public static Fraction operator +(Fraction F1, int _F2)
        {
            Fraction F2 = new Fraction(_F2.ToString() + '/' + 1.ToString());
            return F1+F2;
        }

        public static Fraction operator +(int _F1, Fraction F2)
        {
            Fraction F1 = new Fraction(_F1.ToString() + '/' + 1.ToString());
            return F1 + F2;
        }

        public override string ToString()
        {
            return numerator.ToString() + '/' + denominator.ToString();
        }

    }

C#:

static class Program
    {
        static void Main(string[] args)
        {

            int N = 1; //N=Number of values received/generated.
            int ReceivedValue = GetNextNumber();

            if (args.Length > 0) { N = Convert.ToInt32(args[0]); } 

            Console.WriteLine("");
            Console.WriteLine("N={0},Value={1}", N.ToString(), ReceivedValue.ToString());

            Console.WriteLine(SelectNumber(new Fraction(string.Format("1/{0}", N)), ReceivedValue).ToString());

            System.Threading.Thread.Sleep(3000); //Increased timer to make more human readable.

            Main(new string[] {(N + 1).ToString()});
        }

        static int GetNextNumber()
        {
            int ArbitraryValue = 100; //May be any value, dynamic or static.
            Random RGen = new Random();
            int RValue = RGen.Next(1, ArbitraryValue);
            RGen = null;
            return RValue;
        }

        static int SelectNumber(Fraction P, int LastReceivedValue) //P=Probability. 1/N
        {
            int N = P.denominator;

            Random RGen = new Random();
            if (N == 1) { return 1; }
            else
            {
                int RValue = RGen.Next(1, N);
                RGen = null;
                if (!(RValue <= LastReceivedValue)) { return SelectNumber(P, LastReceivedValue); } else { return RValue; };
            }            
        }
    }