我的面试问题是这样的:

给定一个包含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.

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


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


当前回答

通过在某种树结构中存储未访问的整数范围,可以在读取现有整数后加快查找丢失的整数的速度。

首先存储[0..]4294967295],每次读取一个整数,你拼接它所在的范围,当它变成空的时候删除一个范围。最后,你得到了在范围内缺少的精确的整数集。所以如果你把5作为第一个整数,你会得到[0..4]和[6..4294967295]。

这比标记位要慢得多,所以它只适用于10MB的情况,前提是你可以将树的较低级别存储在文件中。

存储这种树的一种方法是使用b -树,其范围的开始作为键,范围的结束作为值。最坏的情况是当你得到的都是奇数或偶数时,这意味着要为树存储2^31个值或几十GB……哎哟。最好的情况是一个排序文件,其中您只需要为整个树使用几个整数。

所以这并不是正确的答案,但我想我应该提到这种方法。我想我面试不及格;-)

其他回答

这是个陷阱问题,除非引用不当。只需要通读文件一次,得到最大整数n,并返回n+1。

当然,您需要一个备份计划,以防n+1导致整数溢出。

统计信息算法解决这个问题的次数比确定性方法少。

如果允许使用非常大的整数,则可以生成一个在O(1)时间内可能唯一的数字。像GUID这样的伪随机128位整数只会与集合中现有的40亿个整数中的一个发生碰撞,这种情况的概率不到640亿亿亿分之一。

If integers are limited to 32 bits then one can generate a number that is likely to be unique in a single pass using much less than 10 MB. The odds that a pseudo-random 32-bit integer will collide with one of the 4 billion existing integers is about 93% (4e9 / 2^32). The odds that 1000 pseudo-random integers will all collide is less than one in 12,000 billion billion billion (odds-of-one-collision ^ 1000). So if a program maintains a data structure containing 1000 pseudo-random candidates and iterates through the known integers, eliminating matches from the candidates, it is all but certain to find at least one integer that is not in the file.

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

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

根据原题中目前的措辞,最简单的解决方法是:

找到文件中的最大值,然后加上1。

也许我完全没有理解这个问题的重点,但是您想从一个已排序的整数文件中找到一个丢失的整数吗?

喔…真的吗?让我们想想这样的文件会是什么样子:

1 2 3 4 5 6…第一个丢失的号码……等。

这个问题的解决办法似乎微不足道。