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 to store all of them, but you > should be ready with k numbers whenever prompted, such that all have been > selected with equal probability. Say, when you were prompted, n numbers have > already passed, each of your selected k numbers should have 1/n as the > selection probablity. > > Of course, you can store k numbers from that tape as the tape is > progressing, so that you can present them when prompted. > > ------------------------------ > Try the new Yahoo! India Homepage. Click > here<http://in.rd.yahoo.com/tagline_metro_1/*http://in.yahoo.com/trynew> > . > > > -- <<Bharath>> --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
