我的面试问题是这样的:

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

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


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


当前回答

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

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到4294967295开始。 计算中点。 遍历文件,计算有多少数字等于、小于或高于中点值。 如果没有相等的数字,你就完了。中点数就是答案。 否则,选择数字最少的范围,并使用这个新范围重复第2步。

这将需要对文件进行多达32次线性扫描,但它只使用几个字节的内存来存储范围和计数。

这本质上与Henning的解决方案相同,除了它使用两个箱子而不是16k。

关于这个问题的详细讨论已经在Jon Bentley的“第一栏”中讨论过。“编程珍珠”Addison-Wesley第3-10页

Bentley讨论了几种方法,包括外部排序,使用几个外部文件的归并排序等,但Bentley建议的最佳方法是使用位字段的单次传递算法,他幽默地称之为“神奇排序”:) 来看看这个问题,40亿个数字可以表示为:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

实现bitset的代码很简单:(取自解决方案页面)

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentley的算法只对文件进行一次传递,在数组中设置适当的位,然后使用上面的测试宏检查这个数组以找到缺失的数字。

如果可用内存小于0.466 GB, Bentley建议使用k-pass算法,根据可用内存将输入划分为不同的范围。举一个非常简单的例子,如果只有1个字节(即处理8个数字的内存)可用,并且范围从0到31,我们将其分为0到7、8-15、16-22等范围,并在每次32/8 = 4次传递中处理这个范围。

HTH.

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

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

Surely, and speaking with limited experience (just started learning java at Uni) you can run trhough one set (barrel) of int, and if number not found dispose of barrel. This would both free up space and run a check through each unit of data. If what you are looking for is found add it to a count variable. Would take a long time but, if you made multiple variables for each section and run the check count through each variable and ensure they are exiting/disposing at the same time, the variable storage should not increase? And will speed up the check process. Just a thought.

我可能读得太仔细了,但问题是“生成一个不包含在文件中的整数”。我只是对列表进行排序,并在最大的条目上加1。Bam,一个没有包含在文件中的整数。