我的面试问题是这样的:

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

出于某种原因,当我读到这个问题时,我想到了对角化。假设是任意大的整数。

Read the first number. Left-pad it with zero bits until you have 4 billion bits. If the first (high-order) bit is 0, output 1; else output 0. (You don't really have to left-pad: you just output a 1 if there are not enough bits in the number.) Do the same with the second number, except use its second bit. Continue through the file in this way. You will output a 4-billion bit number one bit at a time, and that number will not be the same as any in the file. Proof: it were the same as the nth number, then they would agree on the nth bit, but they don't by construction.

我想出了下面的算法。

我的想法是:遍历整个整数文件一次,对每个位位置数0和1。0和1的数量必须是2^(numOfBits)/2,因此,如果数量比预期的少,我们可以使用我们的结果数。

例如,假设整数是32位,那么我们需要

int[] ones = new int[32];
int[] zeroes = new int[32];

对于每个数字,我们必须迭代32位,并增加0或1的值:

for(int i = 0; i < 32; i++){
   ones[i] += (val>>i&0x1); 
   zeroes[i] += (val>>i&0x1)==1?0:1;
}

最后,在文件处理后:

int res = 0;
for(int i = 0; i < 32; i++){
   if(ones[i] < (long)1<<31)res|=1<<i;
}
return res;

注意:在某些语言中(如Java) 1<<31是负数,因此,(长)1<<31是正确的方法

如果在[0,2 ^x - 1]范围内少了一个整数,那么就把它们一起xor。例如:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(我知道这并不能完全回答这个问题,但这是对一个非常相似的问题的一个很好的回答。)

假设“整数”表示32位:10mb的空间足以让您计算输入文件中有多少个数字,具有任何给定的16位前缀,对于所有可能的16位前缀,在一次通过输入文件。至少有一个桶被击中的次数少于216次。执行第二次传递,以查找该bucket中哪些可能的数字已经被使用。

如果它意味着超过32位,但仍然是有限的大小:执行上述操作,忽略所有恰巧落在(有符号或无符号;32位范围。

如果“integer”指的是数学整数:通读输入一次,记录你见过的最长数字中最大的数字长度。当你完成后,输出最大值加1是一个多一位的随机数。(文件中的一个数字可能是一个大于10mb的大字节,但如果输入是一个文件,那么您至少可以表示任何适合它的长度)。