Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 9, 2013

Picking K elements randomly


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.



claimtoken-52ac74fbddf1e

3 comments:

  1. for problem 1:
    first 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).

    ReplyDelete
  2. Problem 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)

    Problem 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)

    ReplyDelete
  3. I think Reservoir Algorithm will work - http://en.wikipedia.org/wiki/Reservoir_sampling

    ReplyDelete