數(shù)據(jù)分析師常見的10道面試題(2)

　　然后將這40億個(gè)數(shù)分成兩類:

　　1.最高位為0

　　2.最高位為1

　　并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)<=20億，而另一個(gè)>=20億(這相當(dāng)于折半了);

　　與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找

　　再然后把這個(gè)文件為又分成兩類:

　　1.次最高位為0

　　2.次最高位為1

　　并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)<=10億，而另一個(gè)>=10億(這相當(dāng)于折半了);

　　與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。

　　…….

　　以此類推，就可以找到了,而且時(shí)間復(fù)雜度為O(logn)，方案2完。

　　附：這里，再簡(jiǎn)單介紹下，位圖方法：

　　使用位圖法判斷整形數(shù)組是否存在重復(fù)

　　判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。

　　位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個(gè)長(zhǎng)度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個(gè)元素置1，這樣下次再遇到5想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時(shí)置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長(zhǎng)的話效率還能提高一倍。

　　歡迎，有更好的思路，或方法，共同交流。

　　8、怎么在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個(gè)?

　　方案1：先做hash，然后求模映射為小文件，求出每個(gè)小文件中重復(fù)次數(shù)最多的一個(gè)，并記錄重復(fù)次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的一個(gè)就是所求(具體參考前面的題)。

　　9、上千萬或上億數(shù)據(jù)(有重復(fù))，統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的錢N個(gè)數(shù)據(jù)。

　　方案1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進(jìn)行統(tǒng)計(jì)次數(shù)。然后就是取出前N個(gè)出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第2題提到的堆機(jī)制完成。

　　10、一個(gè)文本文件，大約有一萬行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析。

　　方案1：這題是考慮時(shí)間效率。用trie樹統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O(n*le)(le表示單詞的平準(zhǔn)長(zhǎng)度)。然后是找出出現(xiàn)最頻繁的前10個(gè)詞，可以用堆來實(shí)現(xiàn)，前面的題中已經(jīng)講到了，時(shí)間復(fù)雜度是O(n*lg10)。所以總的時(shí)間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的哪一個(gè)。

　　附、100w個(gè)數(shù)中找出最大的100個(gè)數(shù)。

　　方案1：在前面的題中，我們已經(jīng)提到了，用一個(gè)含100個(gè)元素的最小堆完成。復(fù)雜度為O(100w*lg100)。

　　方案2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時(shí)候，采用傳統(tǒng)排序算法排序，取前100個(gè)。復(fù)雜度為O(100w*100)。

　　方案3：采用局部淘汰法。選取前100個(gè)元素，并排序，記為序列L。然后一次掃描剩余的元素x，與排好序的100個(gè)元素中最小的元素比，如果比這個(gè)最小的要大，那么把這個(gè)最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環(huán)，知道掃描了所有的元素。復(fù)雜度為O(100w*100)。

【數(shù)據(jù)分析師常見的10道面試題(2)】相關(guān)文章：

名校英語(yǔ)面試經(jīng)典常見的面試題10-21

經(jīng)典常見面試題分析解答08-14

戴爾�？嫉�12道面試題08-19

德國(guó)公司經(jīng)典面試題(2)07-10

人力資源行業(yè)常見面試題匯總08-20

大數(shù)據(jù)技術(shù)Hadoop面試題,看看你能答對(duì)多少？08-28

常見的工傷糾紛知識(shí)(2)10-26

“垃圾簡(jiǎn)歷”最常見的錯(cuò)誤(2)10-12

考研英語(yǔ)寫作常見錯(cuò)誤(2)09-30

10個(gè)經(jīng)典的Java面試題集合09-20