algorithm - 生成一个不在给定的四十亿中的整数

Question

我得到了这个面试问题:

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 GB memory. Follow up with what you would do if you have only 10 MB of memory.

我的分析:

文件大小为 4×10⁹×4 字节 = 16 GB。

我们可以进行外部排序，从而让我们知道整数的范围。

我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解(看完所有答案后):

假设我们讨论的是 32 位整数，则有 2³² = 4*10⁹ 个不同的整数。

情况 1:我们有 1 GB = 1 * 10⁹ * 8 位 = 80 亿位内存。

解决方案:

如果我们用一位代表一个不同的整数，就足够了。我们不需要排序。

实现:

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 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况 2:10 MB 内存 = 10 * 10⁶ * 8 位 = 8000 万位

Solution:

For all possible 16-bit prefixes, there are 2¹⁶ number of integers = 65536, we need 2¹⁶ * 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.

1. Build the counter of each bucket through the first pass through the file.
2. Scan the buckets, find the first one who has less than 65536 hit.
3. Build new buckets whose high 16-bit prefixes are we found in step2 through second pass of the file
4. Scan the buckets built in step3, find the first bucket which doesnt have a hit.

The code is very similar to above one.

结论: 我们通过增加文件传递来减少内存。

---

<支持> 对那些迟到的人的澄清:正如所问的那样，这个问题并没有说文件中没有包含一个整数——至少大多数人不是这样解释的。不过，评论线程中的许多评论都是关于该任务的变体。不幸的是，将它介绍到评论线程的评论后来被其作者删除了，所以现在看起来孤立的回复只是误解了一切。很困惑，抱歉。

Answer 1

假设“整数”表示 32 位:10 MB 的空间足以让您计算输入文件中有多少个具有任何给定 16 位前缀的数字，对于所有一次通过输入文件时可能的 16 位前缀。至少有一个桶被击中的次数少于 2¹⁶ 次。进行第二次检查以查找该桶中哪些可能的数字已被使用。

如果它表示多于 32 位，但大小仍然有限:按照上述操作，忽略所有恰好落在(有符号或无符号；您的选择)32 位范围之外的输入数字.

如果“整数”表示数学整数:通读一次输入并记录您见过的最长数字的最大数字 长度。完成后，输出最大值加一一个多一位的随机数。 (文件中的其中一个数字可能是一个 bignum，需要超过 10 MB 才能准确表示，但如果输入是一个文件，那么你至少可以表示适合的任何内容的长度它)。