|
|
腾讯笔试题一则( o% [6 a4 Y, N' |' d& [
# m2 q! c/ O2 w一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数0 K5 f m* b+ U% h3 L: }
答:! _9 Q" f; J; |. w
方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。5 {, d& _9 Q2 V( V4 Z
为了简单起见，可以假设都是无符号整数。
0 i3 D2 b1 ^1 O# Y8 _. {分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：
0 |; R( ^6 `) M3 _$ j１）分配５００ＭＢ内存buf，初始化为０9 m N9 i8 P$ T5 H% R8 b
２）unsigned int x=0
M1 [3 N* k) B5 s4 ?1 ~ g1 l
腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html
( L u1 k6 z* m: S2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html
8 d) Y8 r* _2 y, }4 a, m腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html |
|
IP卡
狗仔卡
发表于 2012-4-12 16:34
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡