Have a list of size 1 million....start reading numbers from the hard disk....until the list size reaches 1 million, push the item into the list (use insertion sort)....at the end of 1 million entries, it wil be sorted.....lets say the list having numbers like (10,11,12,...,20,...etc).... continue reading from the HDD, insert the element in to the list at the right place (using insertion sort) only if the last element is greater than the newly read element.....(btw, last element has been thrown out - by pushing the entires right side after placing the new one).....
at the end of reading all the entries...we will have a list of smallest 1 million entires... i believe i have explained clearly.... On Sat, Sep 5, 2009 at 5:41 PM, sharad kumar <[email protected]>wrote: > divide the horses into 5 groups a,b,c,d,e number them as a1,a2,..,a5, > b1..b5, c1..c5, d1..d5 and e1..e5. Conduct 5 races within the groups. Youve > 15 winners (3 frm each race). a1,a2,a3,b1,b2,b3...,e1,e2,e3. Now conduct a > sixth race among a1,b1,c1,d1,e1. Youve 3 winners say they are a1,b1,c1. Now > you can eliminate all the d's and e's. since d1 and e1 isnt even in the top > 3. You also eliminate b3,c2,c3 as they cannot be in the top 3 as there are > already altleast 3 horses faster than them. After this elimination, you are > left with a1,a2,a3,b1,b2,c1. > a1 is the fastest of them all. So conduct a 7th race among a2,a3,b1,b2,c1 > to determine the next 2. > > > On Sat, Sep 5, 2009 at 5:18 PM, manoj janoti <[email protected]> wrote: > >> If someone gives the answer of this puzzle can easily solve this puzzle. >> >> There are 25 horses. >> We have to find out 3 most fastest horses among them. >> But there are only 5 tracks in the field i.e only 5 horses can run at a >> time. >> >> manoj >> >> On Sat, Sep 5, 2009 at 4:40 PM, Ajith G <[email protected]> wrote: >> >>> i think this doesnt work. >>> consider first million numbers all of them to be 1. >>> next million number(all of them ) to be 2. >>> and so on.... >>> >>> if you take first element from each million then you will end up with >>> 1,2........ >>> but the smallest million numbers are all 1. >>> >>> >>> >>> >>> >>> >>> >>> On Fri, Sep 4, 2009 at 8:29 AM, viswanath ramakrishnan < >>> [email protected]> wrote: >>> >>>> >>>> >>>> Q.3: Given a set of 1 Trillion integers on hard disk, find the >>>> smallest 1 >>>> million of them. You can fit at most 1 million integers in memory at a >>>> time. >>>> State the fastest solution you can think of. >>>> >>>> take the first 1 million out of 1 trillion and sort the 1 million >>>> integersand store it back in the hard disk. >>>> In this way carry on the sorting for every group of 1 million integers >>>> and store it in the hard drive . Now groups of 1 million integers are >>>> sorted upto 1 trillion. >>>> now compare the first element of all the sorted groups the minimum of >>>> them is the minimum of the 1 trillion. store it as the first element >>>> in the memory. >>>> next take the second element from the group from which the smallest >>>> elemnt came and then check it with all other groups first element. >>>> In this way repeat the procedureuntil the first 1 million is sorted >>>> and stored in the memory. >>>> >>>> correct me if i am wrong..... >>>> >>>> >>>> >>> >>> >>> >> >> >> > > > > -- cheers Jeeva --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
