數據庫招聘筆試題

時間：2024-07-03 05:12:35 面試筆試我要投稿

相關推薦

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段，可以分的段數少一些，這樣在掃描記數段時會快一些，還能節省一些內存。

【數據庫招聘筆試題】相關文章：

微軟招聘試題11-16