@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 <vetribal...@gmail.com> wrote: > @ankit: think u missed heapify.. > time complexity is O(n logn) > > On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal <ankitsamb...@gmail.com> > 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 <varunpahwa2...@gmail.com> >> 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 <varunpahwa2...@gmail.com> >> > wrote: >> >> >> >> @ankit :please explain by taking an example. >> >> >> >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji <vetribal...@gmail.com> >> >> 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 >> >>> <ankitsamb...@gmail.com> >> >>> 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 <duman...@gmail.com> 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 <radhakrishnance...@gmail.com> >> >>>> > 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 <duman...@gmail.com> >> >>>> >> 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 algogeeks@googlegroups.com. >> >>>> >> > To unsubscribe from this group, send email to >> >>>> >> > algogeeks+unsubscr...@googlegroups.com. >> >>>> >> > 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 algogeeks@googlegroups.com. >> >>>> > To unsubscribe from this group, send email to >> >>>> > algogeeks+unsubscr...@googlegroups.com. >> >>>> > 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 algogeeks@googlegroups.com. >> >>>> To unsubscribe from this group, send email to >> >>>> algogeeks+unsubscr...@googlegroups.com. >> >>>> 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 algogeeks@googlegroups.com. >> >>> To unsubscribe from this group, send email to >> >>> algogeeks+unsubscr...@googlegroups.com. >> >>> 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 :: rit2008...@iiita.ac.in >> >> Another Email :: varunpahwa.ii...@gmail.com >> >> >> >> 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 :: rit2008...@iiita.ac.in >> > Another Email :: varunpahwa.ii...@gmail.com >> > >> > 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 algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
