我的面试问题是这样的:

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

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


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


当前回答

2128*1018 + 1(即(28)16*1018 + 1)——这难道不是今天的普遍答案吗?这表示一个不能保存在16eb文件中的数字,这是当前任何文件系统中的最大文件大小。

其他回答

你不需要对它们排序,只需要重复划分它们的子集。

The first step is like the first pass of a quicksort. Pick one of the integers, x, and using it make a pass through the array to put all the values less than x to its left and values more than x to its right. Find which side of x has the greatest number of available slots (integers not in the list). This is easily computable by comparing the value of x with its position. Then repeat the partition on the sub-list on that side of x. Then repeat the partition on the sub-sub list with the greatest number of available integers, etc. Total number of compares to get down to an empty range should be about 4 billion, give or take.

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

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

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

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

为什么要把它弄得这么复杂?你要的是一个文件中没有的整数?

根据指定的规则,您唯一需要存储的是到目前为止在文件中遇到的最大整数。读取整个文件后,返回一个大于1的数字。

不存在触及maxint或任何东西的风险,因为根据规则,对算法返回的整数或数字的大小没有限制。

给定一个包含40亿个整数的输入文件,提供一个算法 生成文件中不包含的整数。假设你 有1gib的内存。接着问如果只有你会怎么做 10内存MiB。 文件大小为4 * 109 * 4字节= 16gib

如果是32位无符号整数

0 <= Number < 2^32
0 <= Number < 4,294,967,296

我建议的解决方案是:c++不进行错误检查

#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    const long SIZE = 1L << 32;

    std::vector<bool> checker(SIZE, false);

    std::ifstream infile("file.txt");  // TODO: error checking

    unsigned int num = 0;

    while (infile >> num)
    {
        checker[num] = true ;
    }

    infile.close();

    // print missing numbers

    for (long i = 0; i < SIZE; i++)
    {
        if (!checker[i])
            cout << i << endl ;
    }

    return 0;
}

复杂性

Space ~ 232 bits = 229 Bytes = 219 KB = 29 MB = 1/2 GB 时间~单次通过 完整性~是

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.