我的面试问题是这样的:

给定一个包含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和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是正确的方法

其他回答

对于10mb内存限制:

将数字转换为二进制表示形式。 创建一个二叉树,其中左= 0,右= 1。 使用二进制表示将每个数字插入树中。 如果已经插入了一个数字,则叶子将已经创建。

完成后,只需使用之前未创建的路径来创建所请求的数字。

40亿数字= 2^32,这意味着10 MB可能不够。

EDIT

优化是可能的,如果已经创建了两个末端叶并且有一个共同的父级,那么可以将它们删除,并且父级标记为不是解决方案。这减少了分支,减少了对内存的需求。

编辑II

没有必要完全构建树。只有在数字相似的情况下才需要构建深度分支。如果我们也砍掉树枝,那么这个解决方案实际上可能有效。

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

如果允许使用非常大的整数,则可以生成一个在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.

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

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.

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

如果恰好有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";
  }
}

检查输入文件的大小,然后输出任何过大而无法用该大小的文件表示的数字。这似乎是一个廉价的技巧,但它是一个创造性的解决面试问题的方法,它巧妙地避开了记忆问题,从技术上讲,它是O(n)。

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

应该打印10位计数- 1,这将永远大于2位计数。从技术上讲,你必须打败的数字是2 bitcount -(4 * 109 - 1),因为你知道文件中还有(40亿- 1)个其他整数,即使使用完美的压缩,它们也会占用至少1位。