腾讯笔试题一则

aftyingjiesheng

腾讯笔试题一则
! q- k% b# u% D6 |
4 t9 g5 ^. G% v2 }+ W8 y" M一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数
答:
* W7 h1 e1 N$ P1 I+ i2 q0 Q方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。
为了简单起见，可以假设都是无符号整数。
分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：
- o0 y, I* e" j+ f9 C6 g$ Q2 Z$ C１）分配５００ＭＢ内存buf，初始化为０
6 i- ~5 w) P& _4 R２）unsigned int x=0
' S5 y3 N5 C2 m, m$ s
腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html
  A. Z+ N  P  v; R8 t2 R# g2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html
  U/ w' f4 h6 _' v" {腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html