CSE Blog - quant, math, computer science puzzles

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

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)

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