我的面试问题是这样的:

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

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


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


当前回答

The simplest approach is to find the minimum number in the file, and return 1 less than that. This uses O(1) storage, and O(n) time for a file of n numbers. However, it will fail if number range is limited, which could make min-1 not-a-number. The simple and straightforward method of using a bitmap has already been mentioned. That method uses O(n) time and storage. A 2-pass method with 2^16 counting-buckets has also been mentioned. It reads 2*n integers, so uses O(n) time and O(1) storage, but it cannot handle datasets with more than 2^16 numbers. However, it's easily extended to (eg) 2^60 64-bit integers by running 4 passes instead of 2, and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly, in which case run time is no longer O(n) but instead is O(n*log n). The method of XOR'ing all the numbers together, mentioned so far by rfrankel and at length by ircmaxell answers the question asked in stackoverflow#35185, as ltn100 pointed out. It uses O(1) storage and O(n) run time. If for the moment we assume 32-bit integers, XOR has a 7% probability of producing a distinct number. Rationale: given ~ 4G distinct numbers XOR'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren't all distinct, the XOR method's probability of success rises.

其他回答

老问题了,但我想知道“非功能性”需求。在我看来,应该给出一个线索——如果这个问题是在其他地方问的,而不是在一本书里,然后继续讨论所有的可能性的利弊。通常情况下,这似乎是在工作面试中问的,让我困惑的是,在不知道软要求的情况下,不可能给出一个明确的答案,即。“查找缺失的数字一定非常快,因为它一秒钟要使用x次。”

我想这样的问题或许可以给出一个合理的答案。

我将所有数字归并排序到一个新文件中,每个int使用4个字节。当然,一开始做起来会很慢。但是它可以用很小的内存量来完成(你不需要把所有内存都保存在RAM中) 使用二进制搜索检查数字是否存在于预排序文件中。因为每个值仍然是4个字节,这没有问题

缺点:

文件大小 第一次排序很慢——但只需要一次

优点:

查找起来非常快

这又是一个非常适合写书的问题。但我认为,当要解决的问题还不完全清楚时,在寻求单一的最佳解决方案时,这是一个奇怪的问题。

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

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

如果您不假设32位约束,则只返回一个随机生成的64位数字(如果您比较悲观,则返回128位数字)。碰撞的几率是1 / 2^64/(4*10^9)= 4611686018.4(大约40亿分之一)。大多数时候你都是对的!

(开玩笑的…种)。

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

The simplest approach is to find the minimum number in the file, and return 1 less than that. This uses O(1) storage, and O(n) time for a file of n numbers. However, it will fail if number range is limited, which could make min-1 not-a-number. The simple and straightforward method of using a bitmap has already been mentioned. That method uses O(n) time and storage. A 2-pass method with 2^16 counting-buckets has also been mentioned. It reads 2*n integers, so uses O(n) time and O(1) storage, but it cannot handle datasets with more than 2^16 numbers. However, it's easily extended to (eg) 2^60 64-bit integers by running 4 passes instead of 2, and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly, in which case run time is no longer O(n) but instead is O(n*log n). The method of XOR'ing all the numbers together, mentioned so far by rfrankel and at length by ircmaxell answers the question asked in stackoverflow#35185, as ltn100 pointed out. It uses O(1) storage and O(n) run time. If for the moment we assume 32-bit integers, XOR has a 7% probability of producing a distinct number. Rationale: given ~ 4G distinct numbers XOR'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren't all distinct, the XOR method's probability of success rises.