- 相關推薦
數(shù)據(jù)分析師常見的10道面試題(2)
然后將這40億個數(shù)分成兩類:
1.最高位為0
2.最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=20億，而另一個>=20億(這相當于折半了);
與要查找的數(shù)的最高位比較并接著進入相應的文件再查找
再然后把這個文件為又分成兩類:
1.次最高位為0
2.次最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=10億，而另一個>=10億(這相當于折半了);
與要查找的數(shù)的次最高位比較并接著進入相應的文件再查找。
…….
以此類推，就可以找到了,而且時間復雜度為O(logn)，方案2完。
附：這里，再簡單介紹下，位圖方法：
使用位圖法判斷整形數(shù)組是否存在重復
判斷集合中存在重復是常見編程任務之一，當集合中數(shù)據(jù)量比較大時我們通常希望少進行幾次掃描，這時雙重循環(huán)法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。
歡迎，有更好的思路，或方法，共同交流。
8、怎么在海量數(shù)據(jù)中找出重復次數(shù)最多的一個?
方案1：先做hash，然后求模映射為小文件，求出每個小文件中重復次數(shù)最多的一個，并記錄重復次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復次數(shù)最多的一個就是所求(具體參考前面的題)。
9、上千萬或上億數(shù)據(jù)(有重復)，統(tǒng)計其中出現(xiàn)次數(shù)最多的錢N個數(shù)據(jù)。
方案1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機器的內存應該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統(tǒng)計次數(shù)。然后就是取出前N個出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第2題提到的堆機制完成。
10、一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想，給出時間復雜度分析。
方案1：這題是考慮時間效率。用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，時間復雜度是O(n*le)(le表示單詞的平準長度)。然后是找出出現(xiàn)最頻繁的前10個詞，可以用堆來實現(xiàn)，前面的題中已經(jīng)講到了，時間復雜度是O(n*lg10)。所以總的時間復雜度，是O(n*le)與O(n*lg10)中較大的哪一個。
附、100w個數(shù)中找出最大的100個數(shù)。
方案1：在前面的題中，我們已經(jīng)提到了，用一個含100個元素的最小堆完成。復雜度為O(100w*lg100)。
方案2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時候，采用傳統(tǒng)排序算法排序，取前100個。復雜度為O(100w*100)。
方案3：采用局部淘汰法。選取前100個元素，并排序，記為序列L。然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那么把這個最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環(huán)，知道掃描了所有的元素。復雜度為O(100w*100)。
http://www.szmdbiao.com/【數(shù)據(jù)分析師常見的10道面試題(2)】相關文章：
名校英語面試經(jīng)典常見的面試題10-21
經(jīng)典常見面試題分析解答08-14
戴爾�？嫉�12道面試題08-19
德國公司經(jīng)典面試題(2)07-10
人力資源行業(yè)常見面試題匯總08-20
大數(shù)據(jù)技術Hadoop面試題,看看你能答對多少？08-28
常見的工傷糾紛知識(2)10-26
“垃圾簡歷”最常見的錯誤(2)10-12
考研英語寫作常見錯誤(2)09-30