找到一个不是40亿个给定值的整数

Question

这是一个面试问题：

给定一个包含40亿个整数的输入文件，提供一个算法来生成一个未包含在文件中的整数。假设您有1 GB内存。如果您只有10 MB内存，请跟进您的操作。

我的分析：

文件大小为4×10 9 ×4字节= 16 GB。

我们可以进行外部排序，因此我们可以了解整数的范围。我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解（阅读完所有答案后）：

假设我们正在讨论32位整数。有2 ^ 32 = 4 * 10 9个不同的整数。

情况1：我们有1 GB = 1 * 10 9 * 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);

        }

    }

}

情况2：10 MB内存= 10 * 10 6 * 8位= 8000万位

解决方案：对于所有可能的16位前缀，有2 ^ 16个整数= 65536，我们需要2 ^ 16 * 4 * 8 = 2百万位。我们需要构建65536个桶。对于每个桶，我们需要4个字节来保存所有可能性，因为最坏的情况是所有40亿个整数属于同一个桶。

通过第一次通过文件构建每个桶的计数器。

扫描存储桶，找到第一个命中率低于65536的存储桶。

构建新的存储桶，我们在第二步中通过文件的第二次传递找到了高16位前缀

扫描步骤3中构建的存储桶，找到第一个没有命中的存储桶。

代码与上面的代码非常相似。

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

对那些迟到的人的澄清：问题，并不是说文件中没有包含一个完整的整数 - 至少不是大多数人解释它的方式。但是，评论主题中的许多评论都是关于任务的变化。不幸的是，将其引入评论主题的评论后来被其作者删除了，所以现在看起来孤立的回复只是误解了一切。这很令人困惑。抱歉。

Answer 1

假设“整数”表示32位：具有10 MB的空间足以让您计算输入文件中具有任何给定的16位前缀的数量，对于所有可能的16位前缀，一次通过输入文件。至少有一个桶的击中次数不会超过2 ^ 16次。执行第二遍以查找已使用该存储桶中的哪些可能数字。如果它意味着超过32位，但仍然是有限大小：如上所述，忽略恰好落在（有符号或无符号;您选择的）32位范围之外的所有输入数字。如果“整数”表示数学整数：读取输入一次并跟踪您所见过的最长数字的最大数字长度。完成后，输出最大加一个随机数，该数字还有一个数字。（文件中的一个数字可能是一个超过10 MB的bignum来准确表示，但如果输入是一个文件，那么你至少可以表示适合它的任何东西的长度）。