腾讯笔试题一则

aftyingjiesheng

腾讯笔试题一则

2 A$ p  e) H, @- k" q, X一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数
! c( f5 g" ^* \2 A: e% u* i答:
方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。
8 `3 m2 O  W' b. L8 U! C为了简单起见，可以假设都是无符号整数。
2 o' R3 `9 M: [# g/ J, G分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：
5 \, y& K( [( G' Q) E% r8 |１）分配５００ＭＢ内存buf，初始化为０
２）unsigned int x=0
% v  i; B3 e3 D' W# w
. @! z7 U& X6 d% f$ P4 ~: d腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html
- i. f6 O3 [" n5 D2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html
* Y' ^2 {  @/ F" `/ ]1 i腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html