- 相關推薦
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段，可以分的段數少一些，這樣在掃描記數段時會快一些，還能節省一些內存。
【數據庫招聘筆試題】相關文章：
微軟招聘試題11-16
google招聘筆試題02-18
宜家招聘筆試題02-18
企業招聘筆試題薈萃02-18
幼師招聘筆試題目06-29
IBM社會招聘筆試題02-18
銀行招聘面試題11-26
證券部門招聘筆試題精選11-21
東風日產招聘筆試題02-23
數據庫常見筆試面試題11-11