Databases
StackOverflow2013
Postsdbo
POFind an integer not among four billion given ones
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind an integer not among four billion given ones
    primarykey
    data
    text
    <p>It is an interview question:</p> <blockquote> <p>Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1&nbsp;GB memory. Follow up with what you would do if you have only 10&nbsp;MB of memory.</p> </blockquote> <p>My analysis:</p> <p>The size of the file is 4×10<sup>9</sup>×4 bytes = 16&nbsp;GB.</p> <p>We can do external sorting, thus we get to know the range of the integers. My question is what is the best way to detect the missing integer in the sorted big integer sets?</p> <p>My understanding(after reading all answers):</p> <p>Assuming we are talking about 32-bit integers. There are 2^32 = 4*10<sup>9</sup> distinct integers.</p> <p>Case 1: we have 1&nbsp;GB = 1 * 10<sup>9</sup> * 8 bits = 8 billion bits memory. Solution: if we use one bit representing one distinct integer, it is enough. we don't need sort. Implementation: </p> <pre><code>int radix = 8; byte[] bitfield = new byte[0xffffffff/radix]; void F() throws FileNotFoundException{ Scanner in = new Scanner(new FileReader("a.txt")); while(in.hasNextInt()){ int n = in.nextInt(); bitfield[n/radix] |= (1 &lt;&lt; (n%radix)); } for(int i = 0; i&lt; bitfield.lenght; i++){ for(int j =0; j&lt;radix; j++){ if( (bitfield[i] &amp; (1&lt;&lt;j)) == 0) System.out.print(i*radix+j); } } } </code></pre> <p>Case 2: 10&nbsp;MB memory = 10 * 10<sup>6</sup> * 8 bits = 80 million bits</p> <pre><code>Solution: For all possible 16-bit prefixes, there are 2^16 number of integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build 65536 buckets. For each bucket, we need 4 bytes holding all possibilities because the worst case is all the 4 billion integers belong to the same bucket. step1: Build the counter of each bucket through the first pass through the file. step2: Scan the buckets, find the first one who has less than 65536 hit. step3: Build new buckets whose high 16-bit prefixes are we found in step2 through second pass of the file step4: Scan the buckets built in step3, find the first bucket which doesnt have a hit. The code is very similar to above one. </code></pre> <p>Conclusion: We decrease memory through increasing file pass.</p> <hr> <p><em>A clarification for those arriving late: The question, as asked, does not say that there is exactly one integer that is not contained in the file -- at least that's not how most people interpret it. Many comments in the comment thread <strong>are</strong> about that variation of the task, though. Unfortunately the comment that <strong>introduced</strong> it to the comment thread was later deleted by its author, so now it looks like the orphaned replies to it just misunderstood everything. It's very confusing. Sorry.</em></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USHenning Makholm
    1. USSecureFish
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFind an integer not among four billion given ones
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFind an integer not among four billion given ones
      1. USemboss
      1. VTFavorite
    3. VO
      singulars
      1. POFind an integer not among four billion given ones
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWell, I think sorting is the best way to do it. I'm no expert, though. Sort and keep track of the last number put into the file. If anything is missing, you'll know. (ie you put in 101 then 103 pops up, so you know that the range 102-102 is missing)
      singulars
      1. POFind an integer not among four billion given ones
      1. USRyan Amos
    2. COAre the integers in the file all unique? If so you can do it in `O(n)` time for the 10 MB
      singulars
      1. POFind an integer not among four billion given ones
      1. USPaulpro
    3. CO@trashgod, wrong. For 4294967295 unique integers you'll have 1 integer remaining. To find it, you should summ all integers and substract it from precalculated summ of all possible integers.
      singulars
      1. POFind an integer not among four billion given ones
      1. USNakilon
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload