Describe in more detail how you would use reservoir sampling. What would be the memory requirement? There is a solution to this problem which is O(log S) time and constant memory. Don
On Tuesday, October 8, 2013 2:24:54 PM UTC-4, atul007 wrote: > > can't we use idea of reservoir sampling here ? > > > On Tue, Oct 8, 2013 at 8:18 PM, Don <dond...@gmail.com <javascript:>>wrote: > >> Provide a function which returns a value randomly and uniformly selected >> from the range 0..N-1 excluding values in the array a[S] containing sorted >> values in the same range. A rejection algorithm would work well enough if S >> is much smaller than N, but what if N is large and S is slightly smaller? >> >> Assume that you are given a pseudo-random generator int rnd(int n) which >> returns a pseudo-random number uniformly distributed in the range 0..n-1. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+...@googlegroups.com <javascript:>. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
