Hi, guys ... This is my first blog ... I am completely new to algorithms ... I have just taken it up and I really love it ... I love searching for puzzles each day and try solving them... right now, i am very bad at it ... I hope to improve ASAP and be good one day ... cheers... A problem for u all so that u dont get bored ;)
You are given a set S of n numbers. You must pick a subset S' of k numbers from S such that the probability of each element of S occurring in S' is equal (i.e., each is selected with probability k/n). You may make only one pass over the numbers. What if n is unknown?
Text in white:
If we are still allowed to use O(n) memory, we can use Knuth shuffle to randomly permute the elements of the set as we get them. Whenever we are asked to stop, the answer would be the first k elements of the permutation.
In white:
O(k) memory is sufficient -- keep first K elements, and then for i-th element put it into random position with probability k/i, and discard otherwise.