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 ankitsamb...@gmail.comwrote: @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.
Re: [algogeeks] Re: Million Numbers
@ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote: @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.comwrote: @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. -- 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
@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 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. -- 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
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.comwrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote: @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.comwrote: @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.
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 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.
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 ankitsamb...@gmail.comwrote: 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
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 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
[algogeeks] Re: Million Numbers
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 ankitsamb...@gmail.com 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 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
[algogeeks] Re: Million Numbers
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.
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 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.
[algogeeks] Re: Million Numbers
Create a range tree, pruning out as needed to stay in the memory constraint. Don On Jun 9, 6:24 am, 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.
