我的面试问题是这样的:

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

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


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


当前回答

我认为这是一个已解决的问题(见上文),但还有一个有趣的情况需要记住,因为它可能会被问到:

如果恰好有4,294,967,295(2^32 - 1)个没有重复的32位整数,因此只有一个缺失,有一个简单的解决方案。

从0开始计算运行总数,对于文件中的每个整数,将该整数加上32位溢出(实际上,runningTotal = (runningTotal + nextInteger) % 4294967296)。一旦完成,将4294967296/2加到运行总数中,同样是32位溢出。用4294967296减去这个,结果就是缺少的整数。

“只缺少一个整数”的问题只需运行一次就可以解决,并且只有64位RAM专用于数据(运行总数为32位,读入下一个整数为32位)。

推论:如果我们不关心整数结果必须有多少位,那么更通用的规范非常容易匹配。我们只是生成一个足够大的整数,它不能包含在我们给定的文件中。同样,这只占用极小的RAM。请参阅伪代码。

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

其他回答

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

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

一些消除

一种方法是消除比特,但这实际上可能不会产生结果(很可能不会)。Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

位计数

跟踪比特数;用最少的比特来产生一个值。同样,这也不能保证生成正确的值。

范围的逻辑

跟踪列表的顺序范围(按开始顺序)。范围由结构定义:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

遍历文件中的每个值,并尝试将其从当前范围中删除。这个方法没有内存保证,但是它应该做得很好。

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

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

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

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

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

如果没有大小限制,最快的方法是取文件的长度,并生成文件的长度+1个随机数字(或者只是“11111…”s).优点:您甚至不需要读取文件,并且可以将内存使用最小化到几乎为零。缺点:将打印数十亿个数字。

但是,如果唯一的因素是最小化内存使用,而其他因素都不重要,那么这将是最佳解决方案。它甚至可能让你获得“最严重滥用规则”奖。