tag:blogger.com,1999:blog-4115025577315673827.post6646067247502595873..comments2019-07-15T17:16:38.146+05:30Comments on CSE Blog - quant, math, computer science puzzles: Picking K elements randomlyUnknownnoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4115025577315673827.post-44944912640342851402014-06-24T01:55:08.706+05:302014-06-24T01:55:08.706+05:30For the second part, Reservoir Sampling would work...For the second part, Reservoir Sampling would work. ThanksPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86133869423555861162014-06-24T01:54:45.227+05:302014-06-24T01:54:45.227+05:30Thanks Sid. Both solutions are bang on! ThanksThanks Sid. Both solutions are bang on! ThanksPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-58313925855195188092014-06-24T01:54:21.364+05:302014-06-24T01:54:21.364+05:30Thanks Himanshu. This is Fisher Yattes Shuffle. Th...Thanks Himanshu. This is Fisher Yattes Shuffle. Thanks - Wiki Link: http://en.wikipedia.org/wiki/Fisher-Yates_shufflePratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12124399559635586672013-12-16T02:46:19.579+05:302013-12-16T02:46:19.579+05:30I think Reservoir Algorithm will work - http://en....I think Reservoir Algorithm will work - http://en.wikipedia.org/wiki/Reservoir_samplingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5522371153682562642013-12-10T11:30:07.690+05:302013-12-10T11:30:07.690+05:30Problem 1: Generate a random number i between 1 an...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)<br /><br />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)Sidhttps://www.blogger.com/profile/11521932239961051207noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-26910540005686112512013-12-10T11:25:56.878+05:302013-12-10T11:25:56.878+05:30for problem 1:
first we pick one element randomly ...for problem 1:<br />first we pick one element randomly from N elements , then another one from remaining N-1 elements..so on..till we get K elements;<br />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.<br />After the K steps our initial array contains random elements (from a[0] to a[k-1]). We don't need any extra space.<br />Time complexity: we are just swapping the random elements. Picking a random element is O(1) (not sure).himanshuhttps://www.blogger.com/profile/06639616508085498004noreply@blogger.com