2015年數(shù)據(jù)庫招聘筆試題

　　題目：

　　在一個(gè)文件中有 10G 個(gè)整數(shù)(32位無符號(hào)數(shù))，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。只寫出思路即可。

　　解答：

　　解題思想：類似于桶排序的思想，將32位無符號(hào)數(shù)分段如每16個(gè)一段，0-15為第1段，16-31為第2段等等，然后統(tǒng)計(jì)各段的數(shù)字的個(gè)數(shù)，然后就可以找到中位數(shù)所在的段了，然后就再掃描一遍(只要讀入處于中位數(shù)所在的段即可)原數(shù)集即可得到中位數(shù)。(當(dāng)然也有中特殊的情況就是：中位數(shù)所在的段的整數(shù)的個(gè)數(shù)大于2G的內(nèi)存，即內(nèi)存還裝不下該段，此時(shí)需要做細(xì)化處理：即再將該段細(xì)分，比如說將該段分為8小段，然后再找中位數(shù)所在的段)。

　　1，把整數(shù)分成256M段，每段可以用64位整數(shù)保存該段數(shù)據(jù)個(gè)數(shù)，256M*8 = 2G內(nèi)存，先清0

　　2，讀10G整數(shù)，把整數(shù)映射到256M段中，增加相應(yīng)段的記數(shù)

　　3，掃描256M段的記數(shù)，找到中位數(shù)的段和中位數(shù)的段前面所有段的記數(shù)，可以把其他段的內(nèi)存釋放

　　4，因中位數(shù)段的可能整數(shù)取值已經(jīng)比較小(如果是32bit整數(shù)，當(dāng)然如果是64bit整數(shù)的話，可以再次分段)，對(duì)每個(gè)整數(shù)做一個(gè)記數(shù)，再讀一次10G整數(shù)，只讀取中位數(shù)段對(duì)應(yīng)的整數(shù)，并設(shè)置記數(shù)。

　　5，對(duì)新的記數(shù)掃描一次，即可找到中位數(shù)。

　　如果是32bit整數(shù)，讀10G整數(shù)2次，掃描256M記數(shù)一次，后一次記數(shù)因數(shù)量很小，可以忽略不記。

　　解釋一下：假設(shè)是32bit整數(shù)，按無符號(hào)整數(shù)處理

　　整數(shù)分成256M段? 整數(shù)范圍是0 - 2^32 - 1 一共有4G種取值，4G/256M = 16，每16個(gè)數(shù)算一段 0-15是1段，16-31是一段，...

　　整數(shù)映射到256M段中? 如果整數(shù)是0-15，則增加第一段記數(shù)，如果整數(shù)是16-31，則增加第二段記數(shù)，...

　　其實(shí)可以不用分256M段，可以分的段數(shù)少一些，這樣在掃描記數(shù)段時(shí)會(huì)快一些，還能節(jié)省一些內(nèi)存。

【數(shù)據(jù)庫招聘筆試題】相關(guān)文章：

微軟招聘試題11-16

google招聘筆試題02-18

宜家招聘筆試題02-18

企業(yè)招聘筆試題薈萃02-18

幼師招聘筆試題目06-29

IBM社會(huì)招聘筆試題02-18

銀行招聘面試題11-26

證券部門招聘筆試題精選11-21

東風(fēng)日產(chǎn)招聘筆試題02-23

數(shù)據(jù)庫常見筆試面試題11-11