**Problem 1:**Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm?

**Problem 2:**Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly.

Update (24 June 2014):

**Solution:**Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks
for problem 1:

ReplyDeletefirst we pick one element randomly from N elements , then another one from remaining N-1 elements..so on..till we get K elements;

One way to code this is..after getting the first element we can swap this element with first element in an array. Now we need to find 2nd random element from a[1] to a[N-1]. Next we swap a[1] & random element.

After the K steps our initial array contains random elements (from a[0] to a[k-1]). We don't need any extra space.

Time complexity: we are just swapping the random elements. Picking a random element is O(1) (not sure).

Thanks Himanshu. This is Fisher Yattes Shuffle. Thanks - Wiki Link: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

DeleteProblem 1: Generate a random number i between 1 and N. Select the ith element, and swap the Nth element with the ith in the array. Now, generate a random number j between 1 and N-1. Select the jth element, and swap the (N-1)th element with the jth in the array. Continue until K. (This is similar to Fisher Yates shuffle)

ReplyDeleteProblem 2: Select the ith element in the stream with probability min(1, K/i). If more than K elements have already been selected, replace any of the existing elements at random. (This is also called Reservoir Sampling)

Thanks Sid. Both solutions are bang on! Thanks

DeleteI think Reservoir Algorithm will work - http://en.wikipedia.org/wiki/Reservoir_sampling

ReplyDeleteFor the second part, Reservoir Sampling would work. Thanks

Delete