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

Question

这是一个面试问题:

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

我的分析:

文件大小为4×10 ⁹ ×4字节= 16 GB.

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

我的理解(阅读完所有答案后):

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

情况1:我们有1 GB = 1*10 ⁹*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 ⁶*8位= 8000万位

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);
        }
    }
}

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

---

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

Answer 1

假设"整数"表示32位:具有10 MB的空间足以让您计算输入文件中具有任何给定的16位前缀的数量,对于所有可能的16位前缀,一次通过输入文件.至少有一个桶的击中次数不会超过2 ^ 16次.执行第二遍以查找已使用该存储桶中的哪些可能数字.

如果它意味着超过32位,但仍然是有限大小:如上所述,忽略恰好落在(有符号或无符号;您选择的)32位范围之外的所有输入数字.

如果"整数"表示数学整数:读取输入一次并跟踪您所见过的最长数字的最大数字长度.完成后,输出最大加一个随机数,该数字还有一个数字.(文件中的一个数字可能是一个超过10 MB的bignum来准确表示,但如果输入是一个文件,那么你至少可以表示适合它的任何东西的长度).

Answer 2

统计通知算法使用比确定性方法更少的通过来解决此问题.

如果允许非常大的整数,则可以生成在O(1)时间内可能唯一的数字.像GUID这样的伪随机128位整数只会与集合中现有的40亿个整数中的一个冲突,而不是每640亿亿个案例中只有一个.

如果整数限制为32位,则可以使用远小于10 MB的单次传递生成一个可能唯一的数字.伪随机32位整数将与40亿现有整数中的一个冲突的几率约为93%(4e9/2 ^ 32).1000个伪随机整数将全部碰撞的几率小于12,000亿亿(1个碰撞的概率^ 1000).因此,如果程序维护包含1000个伪随机候选者的数据结构并迭代已知整数,从候选者中消除匹配,则几乎肯定会找到至少一个不在文件中的整数.

Answer 3

关于这个问题的详细讨论已经在Jon Bentley "Column 1. Cracking the Oyster" 编程中讨论了Pearls Addison-Wesley pp.3-10

Bentley讨论了几种方法,包括外部排序,使用多个外部文件进行合并排序等.但Bentley建议的最佳方法是使用位字段的单程算法,他幽默地称之为"Wonder Sort":)问题,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的算法对文件进行单次传递set,将数组中的相应位调整,然后使用test上面的宏检查此数组以查找缺少的数字.

如果可用内存小于0.466 GB,Bentley建议使用k-pass算法,该算法根据可用内存将输入划分为范围.举一个非常简单的例子,如果只有1个字节(即处理8个数字的存储器)可用且范围从0到31,我们将其分为0到7,8-15,16-22的范围,依此类推并在每个32/8 = 4通行证中处理此范围.

HTH.

Answer 4

由于问题没有指定我们必须找到文件中不存在的最小可能数字,我们只能生成一个比输入文件本身更长的数字.:)

Answer 5

对于1 GB RAM变体,您可以使用位向量.您需要分配40亿位== 500 MB字节数组.对于从输入读取的每个数字,将相应位设置为"1".完成后,迭代这些位,找到第一个仍为"0"的位.它的索引就是答案.

Answer 6

如果它们是32位整数(可能选择约40亿个数字接近2 ^ 32),那么40亿个数字的列表将占用最多93%的可能整数(4*10 ^ 9 /(2 ^ 32)).因此,如果你创建一个2 ^ 32位的位数组,每个位初始化为零(这将占用2 ^ 29字节~500 MB的RAM;记住一个字节= 2 ^ 3位= 8位),读取你的整数列表并为每个int设置相应的位数组元素,从0到1; 然后读取你的位数组并返回仍然为0的第一位.

在RAM较少(~10 MB)的情况下,需要稍微修改此解决方案.对于介于0和83886079之间的所有数字,10 MB~83886080位仍足以为位数组做.因此,您可以读取整数列表; 并且只在位数组中记录0到83886079之间的#s.如果数字是随机分布的; 以极大的概率(它相差100%大约10 ^ -2592069)你会发现缺少int).事实上,如果你只选择数字1到2048(只有256字节的RAM),你仍然会发现一个失败的数字,压倒性的百分比(99.9999999999999999999999999999999999999999999999%)的时间.

但是,让我们说而不是大约有40亿个数字; 你有2 ^ 32 - 1个数字和不到10 MB的RAM; 因此,任何小范围的整数只有很小的可能性不包含该数字.

如果你保证列表中的每个int都是唯一的,你可以将数字相加并用一个#缺省减去总和(1/2)(2 ^ 32)(2 ^ 32-1)= 9223372034707292160找到缺少的int.但是,如果int发生两次,则此方法将失败.

但是,你总能分而治之.一种天真的方法是读取数组并计算前半部分(0到2 ^ 31-1)和后半部分(2 ^ 31,2 ^ 32)的数字数量.然后选择数字较少的范围并重复将该范围分成两半.(假如在(2 ^ 31,2 ^ 32)中有两个较少的数字,那么你的下一个搜索将计算范围内的数字(2 ^ 31,3*2 ^ 30-1),(3*2 ^ 30, 2 ^ 32).继续重复,直到找到一个数字为零的范围并且你有答案.应该通过数组取O(lg N)~32个读数.

那种方法效率低下.我们在每一步中只使用两个整数(或者大约8字节的RAM和一个4字节(32位)整数).一种更好的方法是划分为sqrt(2 ^ 32)= 2 ^ 16 = 65536个bin,每个bin在bin中有65536个数字.每个bin需要4个字节来存储其计数,因此您需要2 ^ 18个字节= 256 kB.所以bin 0是(0到65535 = 2 ^ 16-1),bin 1是(2 ^ 16 = 65536到2*2 ^ 16-1 = 131071),bin 2是(2*2 ^ 16 = 131072到3)*2 ^ 16-1 = 196607).在python中你会有类似的东西:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

通读~40亿整数列表; 并计算每个2 ^ 16箱中有多少总量,并找到一个不包含全部65536个数字的incomplete_bin.然后再读一遍40亿整数列表; 但这次只注意整数在那个范围内; 当你找到它们时翻转一下.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

Answer 7

为什么要这么复杂？你问一个文件中没有的整数？

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

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

Answer 8

这可以使用二进制搜索的变体在非常小的空间中解决.

1. 从允许的数字范围开始,0到4294967295.

2. 计算中点.

3. 循环遍历文件,计算有多少数字相等,小于或高于中点值.

4. 如果没有数字相等,那么你就完成了.中点数是答案.

5. 否则,选择具有最少数字的范围,并使用此新范围从步骤2开始重复.

这将需要通过文件最多32次线性扫描,但它只会使用几个字节的内存来存储范围和计数.

这与Henning的解决方案基本相同,只是它使用两个箱而不是16k.

Answer 9

编辑好的,这并没有完全考虑过,因为它假定文件中的整数遵循一些静态分布.显然他们不需要,但即便如此,也应该尝试这样做:

有大约43亿个32位整数.我们不知道它们是如何在文件中分布的,但最坏的情况是具有最高香农熵的那个:相等的分布.在这种情况下,文件中不出现任何一个整数的概率

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

香农熵越低,这个概率在平均值上越高,但即使对于这种最坏的情况,我们也有90%的机会在随机整数进行5次猜测后找到一个非发生的数字.只需使用伪随机生成器创建此类数字,将它们存储在列表中.然后在int之后读取int并将其与所有猜测进行比较.如果匹配,请删除此列表条目.经过所有文件后,你可能会有不止一个猜测.使用其中任何一个.在罕见的(甚至在最坏情况下为10%的情况下)没有猜测的事件中,获得一组新的随机整数,这次可能更多(10-> 99%).

内存消耗:几十个字节,复杂性:O(n),开销:可以选择,因为大部分时间都花在不可避免的硬盘访问上,而不是比较整数.

实际的最坏情况,当我们不假设静态分布时,每个整数都出现最大值.一次,因为那时文件中不会出现1 - 4000000000 /2³²≈6%的整数.所以你需要一些更多的猜测,但这仍然不会花费大量的内存.

Answer 10

如果您在[0,2 ^ x - 1] 范围内缺少一个整数,那么只需将它们全部放在一起.例如:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(我知道这并不能完全回答这个问题,但对于一个非常相似的问题,这是一个很好的答案.)

Answer 11

他们可能正在寻找你是否听说过概率布隆过滤器,它可以非常有效地确定一个值是否不是一个大集合的一部分,(但只能很有可能确定它是该集合的成员.)

Answer 12

根据原问题中的当前措辞,最简单的解决方案是:

找到文件中的最大值,然后向其中添加1.

Answer 13

用一个BitSet.40个整数(假设最多2 ^ 32个整数)以每字节8个打包到BitSet中是2 ^ 32/2 ^ 3 = 2 ^ 29 =约0.5 Gb.

要添加更多细节 - 每次读取数字时,请在BitSet中设置相应的位.然后,对BitSet进行一次传递,找到第一个不存在的数字.事实上,你可以通过反复选择一个随机数并测试它是否存在来做到这一点.

实际上BitSet.nextClearBit(0)会告诉你第一个非设置位.

查看BitSet API,它似乎只支持0..MAX_INT,因此您可能需要2个BitSet - 一个用于+'ve数字,一个用于-'ve数字 - 但内存要求不会改变.

Answer 14

如果没有大小限制,最快的方法是获取文件的长度,并生成文件的长度+ 1个随机数字(或只是"11111 ..."s).优点:您甚至不需要读取文件,并且可以将内存使用率降至最低.缺点:您将打印数十亿位数字.

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

Answer 15

如果我们假设数字的范围总是2 ^ n(2的偶数幂),则排他性或将起作用(如另一张海报所示).至于原因,我们来证明一下:

理论

给定任何基于0的整数范围,2^n其中元素包含缺少一个元素的元素,您可以通过简单地将已知值相加以产生缺失的数字来找到缺少的元素.

证据

让我们看一下n = 2.对于n = 2,我们可以表示4个唯一的整数:0,1,2,3.它们的位模式为:

• 0 - 00
• 1 - 01
• 2 - 10
• 3 - 11

现在,如果我们看一下,每个位都设置了两次.因此,由于它被设置为偶数次,并且数字的异或将产生0.如果缺少单个数字,则排除 - 或将产生一个数字,当与缺少的数字进行排他时将导致因此,缺失的数字和由此产生的排他性数字完全相同.如果我们删除2,则得到的xor将是10(或2).

现在,让我们看看n + 1.让我们调用每个位的设置次数n,x以及每个位的设置次数n+1 y.值y将等于y = x * 2因为存在x将n+1位设置为0的x元素,以及将n+1位设置为1的元素.并且由于2x将始终为偶数,因此n+1将始终将每个位设置为偶数次.

因此,由于n=2工作和n+1工作,xor方法将适用于所有值n>=2.

基于0的范围算法

这很简单.它使用2*n位的内存,因此对于<= 32的任何范围,2个32位整数将起作用(忽略文件描述符消耗的任何内存).它只传输一次文件.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

任意范围的算法

该算法适用于任何起始编号到任何结束编号的范围,只要总范围等于2 ^ n ...这基本上重新定义范围使其最小值为0.但它确实需要2次通过通过文件(第一个获取最小值,第二个来计算缺少的int).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

任意范围

我们可以将这种修改的方法应用于一组任意范围,因为所有范围将至少跨越2 ^ n的幂.仅当存在一个缺失位时才有效.它需要2次未分类的文件,但每次都会找到一个缺失的数字:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

基本上,将范围重新定义为大约0.然后,它计算要附加的未排序值的数量,因为它计算异或.然后,它将未分类值的数量加1,以处理缺失值(计算缺失值).然后,保持x值为n值,每次递增1,直到n为2的幂.然后结果重新回到原始基数.完成.

这是我在PHP中测试的算法(使用数组而不是文件,但概念相同):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

在一个包含任何值范围的数组中(我测试包括底片),其中一个在该范围内缺失,每次都找到正确的值.

另一种方法

既然我们可以使用外部排序,为什么不检查差距呢？如果我们假设在运行此算法之前对文件进行了排序:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

Answer 16

特技提问,除非被引用不当.只需读取文件一次即可获得最大整数n,然后返回n+1.

当然,如果n+1导致整数溢出,您需要备份计划.

Answer 17

检查输入文件的大小,然后将其输出任何数目是太大,无法由该大小的文件来表示.这似乎是一个廉价的伎俩,但它是面试问题的创造性解决方案,它巧妙地回避了记忆问题,技术上是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 ^bitcount - 1,总是大于2 ^bitcount.从技术上讲,你必须击败的数量是2 ^位计数 - (4×10 ⁹ - 1) ,因为你知道有(4十亿- 1)以外的整数中的文件,甚至与完美的压缩,他们至少会占用每一个.

Answer 18

• 最简单的方法是在文件中找到最小数字,并返回少于1的数字.这使用O(1)存储,并且对于n个数字的文件使用O(n)时间.但是,如果数字范围有限,它将失败,这可能使min-1不是一个数字.

• 已经提到了使用位图的简单直接的方法.该方法使用O(n)时间和存储.

• 还提到了具有2 ^ 16个计数桶的2遍方法.它读取2*n个整数,因此使用O(n)时间和O(1)存储,但它不能处理超过2 ^ 16个数字的数据集.然而,通过运行4次传递而不是2次传递,它很容易扩展到(例如)2 ^ 60个64位整数,并且通过使用尽可能多的存储器并且相应地增加传递次数,很容易适应使用微存储器.哪种情况下运行时间不再是O(n)而是O(n*log n).

• 到目前为止,由rfrankel和ircmaxell提到的将所有数字进行异或的方法回答了stackoverflow#35185中提出的问题,正如ltn100指出的那样.它使用O(1)存储和O(n)运行时.如果目前我们假设32位整数,则XOR产生不同数字的概率为7%.理由:给出~4G不同的数字异或,并且约.300M不在文件中,每个位位置的设置位数有相同的奇数或偶数.因此,2 ^ 32个数字具有与XOR结果相同的可能性,其中93%已经存在于文件中.请注意,如果文件中的数字并非全部不同,则XOR方法的成功概率会增加.

Answer 19

出于某种原因,我一看到这个问题就想到了对角化.我假设任意大整数.

读第一个数字.用零位填充它,直到你有40亿位.如果第一个(高位)位为0,则输出1; 否则输出0.(你真的不需要左键盘:如果数字中没有足够的位,你只输出一个.)对第二个数字做同样的事情,除了使用它的第二个数字.以这种方式继续浏览文件.您将一次输出一个40位的数字,该数字与文件中的任何数字都不相同.证明:它与第n个数字相同,然后他们会同意第n位,但它们不是通过构造.

Answer 20

您可以使用位标志来标记是否存在整数.

遍历整个文件后,扫描每个位以确定该数字是否存在.

假设每个整数是32位,如果完成位标记,它们将方便地适合1 GB的RAM.

Answer 21

仅仅为了完整起见,这是另一个非常简单的解决方案,它很可能需要很长时间才能运行,但使用的内存非常少.

让所有可能的整数是从范围int_min到int_max,而 bool isNotInFile(integer)如果该文件不包含一定的整数,否则为false返回true(在文件中的某些整数,每个整数比较)的功能

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Answer 22

从文件中删除空格和非数字字符并追加1.您的文件现在包含原始文件中未列出的单个数字.

来自Carbonetc的Reddit.

Answer 23

对于10 MB内存约束:

1. 将数字转换为二进制表示.
2. 创建一个二叉树,其中left = 0和right = 1.
3. 使用二进制表示在树中插入每个数字.
4. 如果已插入数字,则已经创建了叶子.

完成后,只需使用之前未创建的路径创建请求的数字.

40亿个数字= 2 ^ 32,意味着10 MB可能还不够.

编辑

优化是可能的,如果已经创建了两个叶子并且具有共同父级,则可以移除它们并且将父标记为不是解决方案.这削减了分支并减少了对内存的需求.

编辑二

也没有必要完全构建树.如果数字相似,您只需要构建深分支.如果我们也削减了分支,那么这个解决方案可能会起作用.

Answer 24

我将回答1 GB版本:

问题中没有足够的信息,所以我先说一些假设:

整数是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;
    }
}