|
|
腾讯笔试题一则# G: } W7 k' z2 J* i
6 N2 n$ c+ F& s1 E! d一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数
" i% E4 [; G1 R) j+ Y答:' g) l& [( N$ I- t9 L- L
方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。: Z3 s8 E0 ^- a
为了简单起见，可以假设都是无符号整数。7 n J! T+ h0 N+ R5 {7 Q' a
分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：1 Z: U9 k# v/ V: n: z
１）分配５００ＭＢ内存buf，初始化为０
& X7 f# [/ G' C9 z２）unsigned int x=0' }% I) `; F3 _% [" U# b9 q# G: W
- H) O& {( |) Q- c3 ]6 ]* Y% _/ k腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html
" m5 o. `4 r, O. a- w2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html2 C! i, Y1 _. A+ j5 `1 r1 O
腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html |
|
IP卡
狗仔卡
发表于 2012-4-12 16:34
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡