我的面试问题是这样的:

给定一个包含40亿个整数的输入文件,提供一种算法来生成一个文件中不包含的整数。假设您有1gb内存。如果你只有10mb的内存,你会怎么做。

我的分析:

文件大小为4×109×4 bytes = 16gb。

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

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

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

假设我们讨论的是32位整数,有232 = 4*109个不同的整数。

情况1:我们有1gb = 1 * 109 * 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);
        }
    }
}

情形二:10mb内存= 10 * 106 * 8bits = 8000万bits

Solution: For all possible 16-bit prefixes, there are 216 number of integers = 65536, we need 216 * 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. Build the counter of each bucket through the first pass through the file. Scan the buckets, find the first one who has less than 65536 hit. Build new buckets whose high 16-bit prefixes are we found in step2 through second pass of the file Scan the buckets built in step3, find the first bucket which doesnt have a hit. The code is very similar to above one.

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


为那些迟到的人澄清一下:这个问题,正如所问的,并不是说有一个整数没有包含在文件中——至少大多数人不是这么理解的。不过,评论线程中的许多评论都是关于任务的变化。不幸的是,把它引入评论线程的评论后来被它的作者删除了,所以现在看起来它的孤儿回复只是误解了一切。这很让人困惑,抱歉。


当前回答

为了完整起见,这里有另一个非常简单的解决方案,它很可能需要很长时间才能运行,但只使用很少的内存。

设所有可能的整数为从int_min到int_max的范围,和 bool isNotInFile(integer)一个函数,如果文件不包含某个整数,则返回true,否则返回false(通过将该特定整数与文件中的每个整数进行比较)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

其他回答

正如Ryan所说,基本上,对文件进行排序,然后遍历整数,当一个值被跳过时,你就有了:)

EDIT at downvotes: OP提到文件可以排序,所以这是一个有效的方法。

我将回答1gb版本:

这个问题没有足够的信息,所以我将先说明一些假设:

整数为32位,取值范围为-2,147,483,648 ~ 2,147,483,647。

伪代码:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

由于问题没有指定我们必须找到文件中不存在的最小数字,我们可以生成一个比输入文件本身更长的数字。:)

从文件中删除空白和非数字字符,并追加1。您的文件现在包含原始文件中没有列出的单个数字。

来自Reddit,作者:Carbonetc。

对于1gb RAM的变体,您可以使用位向量。你需要分配40亿比特== 500 MB字节数组。对于从输入中读取的每个数字,将相应的位设置为“1”。一旦你完成了,遍历比特,找到第一个仍然是“0”的比特。它的索引就是答案。