百度两道面试题

ddvv

我同学在武汉面百度，二面已经完了，还不知道结果。其中有两个问题，看看大家都有什么想法？
1、两个1G的文件，每个文件中都是随机生成的32位无符号整形数，内存600M，如何求出它们的交集和并集？
2、怎么从2.5亿个32位整数中计算有多少个不同的整数，600M内存

先说说我的想法：
1、分别对两个文件进行外排，最后再把两个文件归并。归并的过程中重复的去掉，那么归并的结果就是并集；而在归并过程中两者重复的数字集就是交集。

2、还是外排，多路归并的时候和前面一样去掉重复，最后生成的文件大小size除以4就是不同整数的个数了。

你们的想法又是什么？

zcm211

关注中....

cookis

两个1G文件,,600M内存..
将数据取到内存也是个问题啊..

yg

应该不用那么繁，用位来表达就可以啦

naihe2010

对于第一个问题，我是这样想的。

1G的文件最多含的32位数，应该可以对应到一个256M的char型数组中去。干脆生成两个各含256M的char的数组。（600M足够）

遍历两个1G的文件。
每一个数，都到两个char型的数组里去对应。完成以后，两个char型数组就是排好序的。

然后遍历两个char型数组。a或b只有一个被占据＝＞交集，a和b同时被占据＝＞并集，生成于文件c和d。

georgeying

哈,这两个问题解法其实都一样,很简单.其主要方法都是c语言里面的位操作
因为所有的整数都是32位无符号整数,所以,其范围为0~0xFFFFFFFF,也就是最多有
4G个数字可供选择.如果将这4G个数字从小到大依次排列,每个数字占据一个bit,
那么最多需要4G/8=512M bytes内存(知道百度为什么设定600M内存的大小限制了吧)

好了,聪明的同学应该已经看出来了.
1.我们可以定义一个数组(unsigned char),
其大小为512M,那么,将其全部清零.然后呢,先读入第一个文件,每个数字出现,就
在这超大型数组里面相应bit位置1.然后读取第二个文件,如果想取交集呢,就进行 & 操作,
并集呢就做 | 操作,其所需时间级为 0(N), N为文件大小

2.还是定义这么大的数组,然后读入文件,依次置位,完成后,做一个循环,统计这个超大数组里面有多少位置位了,就ok了........时间还是0(N),完全线型的!

naihe2010

建议楼主看《编程珠机》，第一章就是这种问题。

ddvv

原帖由 georgeying 于 2007-9-27 09:42 发表
哈,这两个问题解法其实都一样,很简单.其主要方法都是c语言里面的位操作
因为所有的整数都是32位无符号整数,所以,其范围为0~0xFFFFFFFF,也就是最多有
4G个数字可供选择.如果将这4G个数字从小到大依次排列,每个 ...

这个方法的确妙啊，没想到这一层，看来对于这种问题不仅仅局限在外排了。。。（原来一看到这种问题就想到外排。）谢了~

030802127

1. cat file1 file2 | sort | uniq   

2. cat file1 file2 | sort | uniq -d

[ 本帖最后由 030802127 于 2007-9-27 12:24 编辑 ]

zcm211

我是菜鸟有 问题
32位数他没说  是二进制的   我不懂这个地方该怎么考虑?