This problem is 'Reservoir Sampling Problem.
http://gregable.com/2007/10/reservoir-sampling.html
On Thu, Sep 17, 2009 at 1:20 PM, manish bhatia mb_mani...@yahoo.com wrote:
There is an infinite tape running, churning out numbers. You are able to
see these numbers one by one, but not allowed
What does optimal balance mean?
In your example case, if you have 10 apples,
put 2 in basket1, 4 in basket2, 4 in basket3 and basket4 gets nothing.
If you have to make sure that, each basket gets at least one apple, then
start distributing apples one by one to each basket until it reaches its
yeah a[i] == a[n-i] will work if you know the length of the list in advance.
What if we dont know the length in advance. One has to to make two passes on
a list ,first to find the length or midpoint and another pass for
comparison.
Can we do it in a single pass?
On Tue, Sep 8, 2009 at 9:01
