The numbers are all distinct. they may vary from 100,000,000 to 999,999,999 and there are roughly 300 million (ie. 300 * 1000,000 numbers approx.). So there are 600*1000,000 number which are not in the file and we are asked to return any one these 600*1000,000 numbers given the memory constraints. Moreover the numbers are in random order.
On Thu, Jun 23, 2011 at 11:10 PM, Liang Ge <[email protected]> wrote: > I think we might need to be more specific about this problem > > 1) Are all these number distinct, i.e. if there are duplicate number in > these numbers? > 2) Is there only one number missing? > 3) do we know the range of these numbers for example n=300million > > If yes to question 1)-3) we could try xor method, it only takes some > bytes O(n) time, O(1) space > > In general: xor1=xor1^x[0]^...,x[n-1] > then xor1=xor1^1,...,n > then return xor1 (we can read all element from file sequentially) > > If no to question 2, we could try this: if we know the range: 1...n, then > sequentially read the number, if it is less than n/2, we output to file A > other wise to file B. We count the size of file A and file B. If file A's > size is less than n/2, then the missing number is in file A. Then we read > number from file A, proceed the above procedure, test with number n/4. The > procedure goes on until we find the missing. The method only works on there > is no duplicate in the numbers. > > > > > > > > > On Thu, Jun 23, 2011 at 11:17 AM, atul purohit > <[email protected]>wrote: > >> Hi, >> >> While external sorting is a probable way to sort it. Still it changes the >> content and time complexity will be > O(n). It is a trivial job to copy the >> entire file and do the sorting and find a number which is not present in >> file but I am looking for a solution which essentially does the job in O(n). >> >> Thanks. >> Atul >> On Thu, Jun 23, 2011 at 6:59 PM, Douglas Diniz <[email protected]> wrote: >> >>> If the file is sorted, use binary search. Divide the file in blocks of >>> 2MB. Choose the blocks using binary search, an inside the block use >>> binary search again to find the number. >>> >>> If the file isn't sorted, sort the file with cosequential process, >>> then use binary search. >>> To learn cosequential process see the book File Structure from Folk. >>> With cosequential process you can sort a terabyte file with only 100 >>> bytes of Ram, for example. >>> >>> Or you can divide the file in blocks of 2MB or less and check all this >>> blocks for the number. >>> >>> On Thu, Jun 23, 2011 at 9:59 AM, atul purohit <[email protected]> >>> wrote: >>> > >>> > Hi, >>> > Can someone explain me how to do this. >>> > Given a file containing roughly 300 million 9-digit numbers. Find a >>> 9-digit >>> > number that isn't present in the file.You have unlimited drive space >>> but >>> > only 2MB of RAM available. >>> > I suppose we have to use bit-vectors n all but still couldnt figure out >>> a >>> > proper way. A few steps or an algo will be great. >>> > Cheers, >>> > Atul >>> > >>> > -- >>> > 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. >>> > >>> >>> >>> >>> -- >>> ------------------------------------------------------------------- >>> Douglas Gameiro Diniz >>> Engenheiro de Computação - 2003 - UNICAMP >>> >>> Mobile: (19) 92158777 >>> Gtalk: dgdiniz >>> Msn: [email protected] >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> >> Atul Purohit >> >> -- >> 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. > -- Atul Purohit -- 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.
