2015年數(shù)據(jù)庫(kù)招聘筆試題
題目:
在一個(gè)文件中有 10G 個(gè)整數(shù)(32位無(wú)符號(hào)數(shù)),亂序排列,要求找出中位數(shù)。內(nèi)存限制為 2G。只寫出思路即可。
解答:
解題思想:類似于桶排序的思想,將32位無(wú)符號(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ù),按無(wú)符號(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)存。
【2015年數(shù)據(jù)庫(kù)招聘筆試題】相關(guān)文章:
企業(yè)招聘面試筆試題03-19
銀行招聘英語(yǔ)面試題04-03
2017教師招聘筆試題庫(kù)08-15
護(hù)士招聘常見陷阱03-26
招聘中常見陷阱03-15
招聘面試技巧陷阱03-14
求職預(yù)防“招聘陷阱”08-20
2017筆試各題型答題技巧07-10