腾讯实习招聘面试题-软件开发

aftyingjiesheng

腾讯实习招聘面试题-软件开发


9 B2 |: J) `6 L" _1 Szz
: m+ i$ X" L* J* y; \

* Q. u4 t' |; z1 q7 V大部分是说说你自己的思想：
' q, H+ B6 z/ \( Z0 N, o! R" e1，一亿个数中取中位数
8 m. P( [. v& q0 n8 a! l( i2，一万个手机号有两个重复的，让你找出来
) m  C$ }5 @5 u2 _4 Y3，求二叉树中两节点的最长路径

9 b; x6 Y+ I7 ?5 ]% V5 g2 M1.有一亿个随机数，不排序如何找出其中位数
( z, R7 v" F' _' ~# S题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。
) X: i# D* G9 l/ t1 Y
! z7 K7 g" \3 z5 j. x5 `; X关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
, }$ Q. a0 C+ `! J6 L( I
% a6 e5 C/ O  ~: D1 n* F/ r( W/ n4 p分析：明显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。
1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。

" _( z; f6 U) X4 {; ^( o2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。
4 h6 A6 m, W0 E) S
3. 接上，对于N个数和K个数都不能一次读进内存的情况，《编程之美》里给出一个方案：设k<K,且k个数可以完全读进内存，那么先构建k个数的堆，先找出第0到k大的数，再扫描一遍数组找出第k+1到2k的数，再扫描直到找出第K个数。虽然每次时间大约是nlog(k)，但需要扫描ceil(K/k) 次，这里要扫描5次。
& Y, G, @- Y6 K* [
; a; f' p. F! V解法：首先假设是32位无符号整数。
+ I+ `* C" d2 x1. 读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。
说明：整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M = 16）种值，每16个值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。
" W5 I/ d! \6 A5 |
/ s" V5 n) [8 T% z2. 从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。
, {: s5 @1 n  E( |
3. 再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。

4. 对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。
6 @1 I; a4 L% r, l3 `+ h, T
4 {& H: |6 Y( G/ a9 f/ C总结：
9 d( u! _) N' T5 `4 |9 }1 T! L1.以上方法只要读两遍整数，对每个整数也只是常数时间的操作，总体来说是线性时间。
3 z' I1 M2 T: Z* K1 }: m- Z8 ?9 l
6 N7 d1 l: J+ d2 [2. 考虑其他情况。
$ J& n$ q+ [4 p& k* F若是有符号的整数，只需改变映射即可。若是64为整数，则增加每个区段的范围，那么在第二次读数时，要考虑更多的计数。若过某个计数溢出，那么可认定所在的区段或代表整数为所求，这里只需做好相应的处理。噢，忘了还要找第5G+1大的数了，相信有了以上的成果，找到这个数也不难了吧。
. ?& b  }# [7 ]# {
+ n% h9 v/ U+ r( c  B7 U* i( o9 u3. 时空权衡。
& V2 E2 `1 s- m0 \花费256个区段也许只是恰好配合2GB的内存（其实也不是，呵呵）。可以增大区段范围，减少区段数目，节省一些内存，虽然增加第二部分的对单个数值的计数，但第一部分对每个区段的计数加快了（总体改变？？待测）。

( `7 j, k1 l, h! f/ n) u4. 映射时尽量用位操作，由于每个区段的起点都是2的整数幂，映射起来也很方便。
9 d3 e7 y" p# a! B, o
+ ]) g) \6 ~8 B) l/ e5 R4 e$ O0 @2.假设有一个应用程序A,现要设计一个应用程序B来动态 测试A，问如何设计这个软件？
9 A0 W4 G  ?- t  E0 P9 ~. f9 k
2 }. n) l- t- j3 N  f% p应聘腾讯面试问题靠记忆整理（四次面试）：http://bbs.aftjob.com/thread-37097-1-1.html
腾讯2010实习面试全纪录——终于结束了：http://bbs.aftjob.com/thread-612336-1-1.html

% t% b  `1 p- u! q* R腾讯求职交流俱乐部：http://bbs.aftjob.com/group-47-1.html