2015年数据库招聘笔试题

题目

2015年数据库招聘笔试题

在一个文件中有 10G 个整数(32位无符号数),乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可。

解答:

解题思想:类似于桶排序的思想,将32位无符号数分段如每16个一段,0-15为第1段,16-31为第2段等等,然后统计各段的数字的个数,然后就可以找到中位数所在的段了,然后就再扫描一遍(只要读入处于中位数所在的段即可)原数集即可得到中位数。(当然也有中特殊的情况就是:中位数所在的段的整数的个数大于2G的内存,即内存还装不下该段,此时需要做细化处理:即再将该段细分,比如说将该段分为8小段,然后再找中位数所在的`段)。

1,把整数分成256M段,每段可以用64位整数保存该段数据个数,256M*8 = 2G内存,先清0

2,读10G整数,把整数映射到256M段中,增加相应段的记数

3,扫描256M段的记数,找到中位数的段和中位数的段前面所有段的记数,可以把其他段的内存释放

4,因中位数段的可能整数取值已经比较小(如果是32bit整数,当然如果是64bit整数的话,可以再次分段),对每个整数做一个记数,再读一次10G整数,只读取中位数段对应的整数,并设置记数。

5,对新的记数扫描一次,即可找到中位数。

如果是32bit整数,读10G整数2次,扫描256M记数一次,后一次记数因数量很小,可以忽略不记。

解释一下:假设是32bit整数,按无符号整数处理

整数分成256M段? 整数范围是0 - 2^32 - 1 一共有4G种取值,4G/256M = 16,每16个数算一段 0-15是1段,16-31是一段,...

整数映射到256M段中? 如果整数是0-15,则增加第一段记数,如果整数是16-31,则增加第二段记数,...

其实可以不用分256M段,可以分的段数少一些,这样在扫描记数段时会快一些,还能节省一些内存。