Re: [algogeeks] Re: Million Numbers
@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 wrote: > @ankit: think u missed heapify.. > time complexity is O(n logn) > > On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal > 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 >> 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 >> > wrote: >> >> >> >> @ankit :please explain by taking an example. >> >> >> >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji >> >> 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 >> >>> >> >>> 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 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 >> > 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 > >> 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 >> >> 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
Re: [algogeeks] Re: Million Numbers
@ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal 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 > 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 > > wrote: > >> > >> @ankit :please explain by taking an example. > >> > >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji > >> 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 > > >>> 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 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 > > 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 >> 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 > 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
Re: [algogeeks] Re: Million Numbers
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 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 > wrote: >> >> @ankit :please explain by taking an example. >> >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji >> 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 >>> 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 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 > 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 >>> >> 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 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, v
Re: [algogeeks] Re: Million Numbers
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 wrote: > @ankit :please explain by taking an example. > > > On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji 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 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 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 >>> > 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 >> >> 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 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 :: rit
Re: [algogeeks] Re: Million Numbers
@Balaji: Sorry, the time complexity was not O(log n). It is O(n). On Thu, Jun 9, 2011 at 11:43 PM, Vetri Balaji 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 > 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 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 >> > 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 > >> 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 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. > -- 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.
Re: [algogeeks] Re: Million Numbers
@ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji 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 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 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 >> > 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 > >> 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 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. -- 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.
Re: [algogeeks] Re: Million Numbers
@ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal 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 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 > > 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 >> 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 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.
Re: [algogeeks] Re: Million Numbers
@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 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 > 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 > 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 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.
