Hey the file has random 300 million numbers (9 digit)...there might be duplicates... not a particular sequence.... out of the many missing numbers we have to print just one... someone please try to understand the solution given alongwith the question.
On Jun 10, 12:49 pm, ankit sambyal <[email protected]> wrote: > @Balaji : No, I didn't miss it. Since we had broken the file > containing 300 million integers into smaller files containing much > less numbers. So, the time complexity of min heapify is not O(logn), > but it is O(log(no. of numbers in smaller file)), which is constant. > Correct if I am wrong. > > > > > > > > On Fri, Jun 10, 2011 at 12:39 AM, Vetri Balaji <[email protected]> wrote: > > @ankit: think u missed heapify.. > > time complexity is O(n logn) > > > On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal <[email protected]> > > wrote: > > >> Lets say we have 9 numbers from 1 to 10 and one number is missing. We > >> hv a RAM which can accomodate only 3 nos. > >> 9,6,7,4,3,2,1,5,10 > >> So, we split the file into 3 smaller files each containing 3 nos. > >> File1: 9,6,7 > >> File2: 4,3,2 > >> File3: 1,5,10 > > >> Now take each file into memory one by one and min heapify > >> them and put them back in the memory. > >> File1: 6,9,7 > >> File2: 2,3,4 > >> File3: 1,5,10 > >> The 1st element in each file is min in each file. > > >> Now make a file temp containing the 1st element of each file and > >> remove the 1st element from the files 1,2 and 3.Min heapify each > >> file.. > >> Temp: 1,6,2 > >> File1: 7,9 > >> File2: 3,4 > >> File3: 5,10 > > >> Now remove 1 from file Temp and take element from File3 because 1 > >> belonged to File3 originally. Again min Heapify them. > >> Temp: 2,6,5 > >> File1: 7,9 > >> File2: 3,4 > >> File3: 10 > > >> Now remove 2 > >> Temp: 3,5,6 > >> File1: 7,9 > >> File2: 4 > >> File3: 10 > > >> Now remove 3 > >> Temp: 4,6,5 > >> File1: 7,9 > >> File2: > >> File3: 10 > > >> Now going on this way we will find that after we remove 7, we could > >> not find 8. So, 8 is the missing no. > > >> Ankit Sambyal > >> BITS Pilani > > >> On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa <[email protected]> > >> wrote: > >> > can anyone explain "Since there > >> > are less than 2^32 numbers in the file there is bound to be one number > >> > in the array that is less than 2^16." in dumanshu's solution. > > >> > On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa <[email protected]> > >> > wrote: > > >> >> @ankit :please explain by taking an example. > > >> >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji <[email protected]> > >> >> wrote: > > >> >>> @ankit: pls explain the time complexity.. > >> >>> i dont think its O(log n) > > >> >>> On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal > >> >>> <[email protected]> > >> >>> wrote: > > >> >>>> @Dumanshu: In each iteration, we r removing the smallest number. If > >> >>>> at any iteration we can't find the next smallest no., it means that > >> >>>> no. is missing..... > > >> >>>> On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu <[email protected]> wrote: > >> >>>> > hey... we have 300 million (9- digit) numbers. So we have to print > >> >>>> > a > >> >>>> > number which isn't already there in the file. > >> >>>> > We are not given that number beforehand. You are saying to check "u > >> >>>> > are going to check whether a number N exist ". > > >> >>>> > On Jun 9, 4:46 pm, radha krishnan <[email protected]> > >> >>>> > wrote: > >> >>>> >> Ma approach is to xor the given number with all numbers in the > >> >>>> >> file > >> >>>> >> !! > >> >>>> >> This takes O(n) > >> >>>> >> I think we cant achieve a complexity <O(n) > >> >>>> >> we have to scan the file at least once > > >> >>>> >> Or move to this problem > >> >>>> >> Instead of a file with numbers > >> >>>> >> you have a stream of numbers > > >> >>>> >> Create a Trie and insert every number from the stream by reversing > >> >>>> >> the > >> >>>> >> digits of the number > >> >>>> >> Now u have a Trie (left as 0 bit && right as 1 bit ) > > >> >>>> >> u are going to check whether a number N exist > >> >>>> >> reverse the bits of N > >> >>>> >> search for appropriate bit in the Trie > >> >>>> >> if all bit are matched then there is a number !! > >> >>>> >> else No > > >> >>>> >> But Space Complexity Of Trie is high we need (32 *(O(n)) assuming > >> >>>> >> each > >> >>>> >> integer is of 32 bits > > >> >>>> >> On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu <[email protected]> > >> >>>> >> wrote: > >> >>>> >> > Given a file containing roughly 300 million social security > >> >>>> >> > numbers(9- > >> >>>> >> > digit numbers) find a 9-digit number that isnt there in the > >> >>>> >> > file. > >> >>>> >> > You > >> >>>> >> > have unlimited drive space but only 2mb of RAM. > > >> >>>> >> > Solution is as follows: > >> >>>> >> > In the first step, we build an array of 2^16 integers that is > >> >>>> >> > initialized to 0 and for every number in the file we take its 16 > >> >>>> >> > most > >> >>>> >> > significant > >> >>>> >> > bit to index into this array and increment that number. Since > >> >>>> >> > there > >> >>>> >> > are less than 2^32 numbers in the file there is bound to be one > >> >>>> >> > number > >> >>>> >> > in the array that is less than 2^16 . This tells us that there > >> >>>> >> > is > >> >>>> >> > at > >> >>>> >> > least one number missing among the possible numbers with those > >> >>>> >> > upper > >> >>>> >> > bits. In the second pass, we can focus only on the numbers that > >> >>>> >> > match > >> >>>> >> > this criterion and use a bit-vector of size 2^16 to identify one > >> >>>> >> > of > >> >>>> >> > the missing numbers. > > >> >>>> >> > Someone plz explain this solution( may be using some small > >> >>>> >> > values > >> >>>> >> > numbers) or suggest another approach. > > >> >>>> >> > -- > >> >>>> >> > 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?hl=en. > > >> >>>> > -- > >> >>>> > 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?hl=en. > > >> >>>> -- > >> >>>> 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?hl=en. > > >> >>> -- > >> >>> 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?hl=en. > > >> >> -- > >> >> Varun Pahwa > >> >> B.Tech (IT) > >> >> 7th Sem. > >> >> Indian Institute of Information Technology Allahabad. > >> >> Ph : 09793899112 ,08011820777 > >> >> Official Email :: [email protected] > >> >> Another Email :: [email protected] > > >> >> People who fail to plan are those who plan to fail. > > >> > -- > >> > Varun Pahwa > >> > B.Tech (IT) > >> > 7th Sem. > >> > Indian Institute of Information Technology Allahabad. > >> > Ph : 09793899112 ,08011820777 > >> > Official Email :: [email protected] > >> > Another Email :: [email protected] > > >> > People who fail to plan are those who plan to fail. > > >> > -- > >> > 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?hl=en. > > >> -- > >> 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?hl=en. > > > -- > > 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?hl=en. -- 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?hl=en.
