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