他们可能想知道你是否听说过概率布鲁姆过滤器，它可以非常有效地确定一个值是否不属于一个大集合，(但只能确定它是集合的一个高概率成员)。

好的，这并没有经过充分的思考，因为它假设文件中的整数遵循某种静态分布。显然他们不需要这样做，但即使这样，也应该试试这个:

有≈43亿个32位整数。我们不知道它们在文件中是如何分布的，但最糟糕的情况是具有最高香农熵的情况:均匀分布。在这种情况下，任何一个整数不出现在文件中的概率为

((2³²-1)/2³²)⁰⁰⁰⁰≈.4

The lower the Shannon entropy, the higher this probability gets on the average, but even for this worst case we have a chance of 90% to find a nonoccurring number after 5 guesses with random integers. Just create such numbers with a pseudorandom generator, store them in a list. Then read int after int and compare it to all of your guesses. When there's a match, remove this list entry. After having been through all of the file, chances are you will have more than one guess left. Use any of them. In the rare (10% even at worst case) event of no guess remaining, get a new set of random integers, perhaps more this time (10->99%).

内存消耗:几十个字节，复杂度:O(n)，开销:neclectable，因为大部分时间将花费在不可避免的硬盘访问上，而不是比较int类型。 当我们不假设静态分布时，实际最坏的情况是每个整数都出现最大值。曾经，因为那时只有 1 - 4000000000/2³²≈6% 所有的整数都不会出现在文件中。因此，您需要更多的猜测，但这仍然不会消耗大量的内存。

一些消除

一种方法是消除比特，但这实际上可能不会产生结果(很可能不会)。Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

位计数

跟踪比特数;用最少的比特来产生一个值。同样，这也不能保证生成正确的值。

范围的逻辑

跟踪列表的顺序范围(按开始顺序)。范围由结构定义:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

遍历文件中的每个值，并尝试将其从当前范围中删除。这个方法没有内存保证，但是它应该做得很好。

我将回答1gb版本:

这个问题没有足够的信息，所以我将先说明一些假设:

整数为32位，取值范围为-2,147,483,648 ~ 2,147,483,647。

伪代码:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

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

这是个陷阱问题，除非引用不当。只需要通读文件一次，得到最大整数n，并返回n+1。

当然，您需要一个备份计划，以防n+1导致整数溢出。