我得到了这个面试问题:
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB memory. Follow up with what you would do if you have only 10 MB of memory.
我的分析:
文件大小为 4×109×4 字节 = 16 GB。
我们可以进行外部排序,从而让我们知道整数的范围。
我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么?
我的理解(看完所有答案后):
假设我们讨论的是 32 位整数,则有 232 = 4*109 个不同的整数。
情况 1:我们有 1 GB = 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);
}
}
}
情况 2:10 MB 内存 = 10 * 106 * 8 位 = 8000 万位
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.
结论: 我们通过增加文件传递来减少内存。
<支持> 对那些迟到的人的澄清:正如所问的那样,这个问题并没有说文件中没有包含一个整数——至少大多数人不是这样解释的。不过,评论线程中的许多评论都是关于该任务的变体。不幸的是,将它介绍到评论线程的评论后来被其作者删除了,所以现在看起来孤立的回复只是误解了一切。很困惑,抱歉。
最佳答案
假设“整数”表示 32 位:10 MB 的空间足以让您计算输入文件中有多少个具有任何给定 16 位前缀的数字,对于所有一次通过输入文件时可能的 16 位前缀。至少有一个桶被击中的次数少于 216 次。进行第二次检查以查找该桶中哪些可能的数字已被使用。
如果它表示多于 32 位,但大小仍然有限:按照上述操作,忽略所有恰好落在(有符号或无符号;您的选择)32 位范围之外的输入数字.
如果“整数”表示数学整数:通读一次输入并记录您见过的最长数字的最大数字 长度。完成后,输出最大值加一一个多一位的随机数。 (文件中的其中一个数字可能是一个 bignum,需要超过 10 MB 才能准确表示,但如果输入是一个文件,那么你至少可以表示适合的任何内容的长度它)。
关于algorithm - 生成一个不在给定的四十亿中的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7153659/