|
|
腾讯笔试题一则: ~% `6 T$ E1 n6 z9 ?' g
! k7 t% U: n# {; {) J, Y
一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数. Y9 {' v/ h3 z5 `
答:
$ m# [' g1 D! }方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。! ~# }7 v( h o) u8 y
为了简单起见，可以假设都是无符号整数。0 i# f7 {3 t* G( B" K
分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：2 e6 q, y: H2 y8 J
１）分配５００ＭＢ内存buf，初始化为０
" S. d7 l8 A3 Y3 t: p) ~２）unsigned int x=0
9 b6 s ?1 C' a4 L; D0 C5 x7 y# `) _' f q: m& z
腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html
+ i$ D5 c1 m5 Q# F3 ~* B2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html
w" w9 N" n# C" K6 s% r腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html |
|
IP卡
狗仔卡
发表于 2012-4-12 16:34
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡