[algogeeks] Re: Interview question: can this be done?
" 4), which will vary the value of k for many times. " I think to cover up this problem.. 1. we can store the starting and ending numbers for every K in another file (with file name of every set) and then sort the file names according to the starting values for every K set, 2. hence creating an index based on the starting values of every set.. 3. so to check if a number is in a set or not we will simply have to perform a binary search on this index 4. and then for every matching set scan that particular set's file to see if the number is present or not. Thus the time for checking multiple instances will be reduced to some extent.. Regards, Prateek. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: here is a problem, I know the answer, but need more explanation to understand it
daizisheng wrote: > Consider the following game. We have a probability distribution on > the following countably infinite deck of cards. > > Card # front backprobability > -- - --- > 1 1 3 1/2 > 2 3 9 1/4 > 3 9 27 1/8 > ... ... ... ... > > A card is selected according to this distribution, and you are shown, > at random, one of its two sides. (Let's say that the number you see > is X, and the one on the other side is Y). You may now decide to > "keep" or > "flip". If you decide "keep", you gain X-Y. If you decide "flip", > then you gain Y-X. > > What to do? If you see 1, the solution is obvious. If you play the game 400 times, how many times will you see 3? Of those occurences, how much do you win or lose if you always flip? So what should you do? Same questions for 9 ... N. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interview question: can this be done?
Kevin wrote: > I get what Terry means now. But it still uses 625/800 = 78% of the > naive method in terms of diskspace (or memory, whatever), so I think > the save is not big enough (the job interview is R&D targeted, which I > assume they want to hear one with "large" saving). > > Prateek's idea is to reduce the time of whole set read in (suppose they > are saved to disk since there are many of them). It should work if the > give k does not show up frequently. For each k, on average, I think we > only need to read in 200/5000 = 4% percent of the whole sets, on 96% > times we only need to check the begining and ending index. But I am > kind of worry for the step 4), which will vary the value of k for many > times. > > beelzebub mentioned "co-prime", interesting. I will think a little bit > more of it. Well it should be 200 numbers randomly chosen not randomly chosen from the initial set :) As you are checking all the numbers of all the sets , when you randomly choose a number why don't check if it is in the bitstring and then discard it. I am not saving anything other than the bitstring. Well i think you need them to be prime, because all the prime factors of a number x ( any number which is not prime ) will be present . --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] here is a problem, I know the answer, but need more explanation to understand it
Consider the following game. We have a probability distribution on the following countably infinite deck of cards. Card # front backprobability -- - --- 1 1 3 1/2 2 3 9 1/4 3 9 27 1/8 ... ... ... ... A card is selected according to this distribution, and you are shown, at random, one of its two sides. (Let's say that the number you see is X, and the one on the other side is Y). You may now decide to "keep" or "flip". If you decide "keep", you gain X-Y. If you decide "flip", then you gain Y-X. What to do? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
