Two problems in sampling from long streams of data. 

1) Uniformly sample one element from a long stream of data. The
eventual length of the stream is unknown. Elements are read one at a
time. On reading an element, you must immediately decide whether to
keep it or to discard it. When the stream runs out, after N items,
each item must have the same probability (1/N) of having been chosen.

You should assume you have access to a function that takes as input an
integer i and returns a randomly chosen integer in the range 0..i-1
inclusive.  This is like rolling an i-sided die numbered from 0 to
i-1.




2) Uniformly sample k elements from a stream. Rules are the same as in
problem 1. You are allowed to keep k elements.  When a new element is
read you must immediately decide whether to discard it or not. When
the stream runs out, each of the items read from the stream must have
probability k/N of being in the sample.