@Don: Note that a[j] - j is the number of non-excluded responses < a[j].
Here is the algorithm I would use:
k = rnd(N - S);
if( k < a[0] )
j = -1;
else
{
Use a binary search to find the largest j with 0 <= j < S such that
a[j] - j <= k;
}
return k + j + 1;
The algorithm uses O(1) ext
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 ?
>
You can do a lot better than N log(N).
Don
On Wednesday, October 9, 2013 2:03:02 PM UTC-4, hppygrry wrote:
>
> What's wrong with just a simple approach with checking the values in the
> array[s] ? Since its already sorted, it takes log(s) time. Assuming S
> approaches N, we are still only lo
What's wrong with just a simple approach with checking the values in the
array[s] ? Since its already sorted, it takes log(s) time. Assuming S
approaches N, we are still only looking at N log (N).
On Tuesday, October 8, 2013 11:24:54 AM UTC-7, atul007 wrote:
>
> can't we use idea of reserv
