国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

常見大數據和空間面試題

Hydrogen / 2441人閱讀

摘要：答案使用，申請一個長度為類型的，每個位置只表示或，該數組占用空間約。遍歷億個數，當前數為，落在區間，對應。

過濾100億黑名單 題目

假設有100億個URL的黑名單，每個URL最多占用64B，設計一個過濾系統，判斷某條URL是否在黑名單里。

要求

不高于萬分之一的判斷失誤率；額外內存不超過30GB

答案

100億個64B的URL需要640GB的內存，顯然直接存哈希表不合理。考慮布隆過濾器，假設有一個長度為m的bit類型數組，如圖所示：

輸入階段：

有k個哈希函數，函數的輸出域S大于或等于m，假設哈希函數彼此獨立，對于同一個輸入(以字符串表示的URL)，經過k個哈希函數的計算結果也是相互獨立。對計算的每一個結果Mod m，將bit array上對應的位置置1，如下：

一個輸入對象會將bitmap某些位置涂黑，處理完所有輸入對象，會將bitmap相當多位置涂黑，至此，布隆過濾器生成完畢，代表之前所有輸入對象的集合。

20億個數中出現最多的數 問題

包含20億個全是32位整數的大文件，在其中找出出現次數最多的數。

要求

內存限制：2GB

答案

將20億個數用hash函數分成16個文件。然后統計每個小文件中，哪個數字出現次數最多。最后再比較每個小文件的次數最多的數。（本題分成16個也是根據題目來的?？紤]最極端情況。20億個數都不同）32位的整數要占4b,key占4b，value占4b。共8b。內存只有2G。所以大概每個小文件存2億條。就需要10個小文件。但是hash函數必須2的n次方。所以2的4次方。16個

40億個數找沒出現的數 問題

有一個包含40億個無符號整數的文件，最多使用1GB內存，找到所有沒出現的數

分析

最差情況，40億個數都不同，哈希表保存出現過的數，需要內存4B*40億，大約16GB內存。

答案

使用bitmap，申請一個長度為4294967295bit類型的bitArray，每個位置只表示0或1，該數組占用空間約500MB。遍歷這20億個數，例如遇到7000，就將bitArray[7000]置1。遍歷完成后，再依次遍歷bitArray，哪個位置沒有置1，哪個數就不在40億個數中。

40億個數找第一個沒出現的數 。內存只有10M 答案

具體的，第一次遍歷，申請長度64的整形數組countArr[0...63]，統計每個區間計數增加。例如，當前數是34225522090，34225522090/67108864=51，countArr[51]++。遍歷完之后，必定有一個countArr[i]小于67108864，表示i區間內至少有一個數沒出現過。此時countArr[]使用的內存是64*4B。

假設在37區間有一個數沒出現，申請一個長度為67108864的bitmap，內存大約8MB，記為bitArr[0~67108863]。再一次遍歷40億個數，只關心37區間的數，記為num。將bitAry[num-6710886437]的值置位1。遍歷完之后，bitArr必然有沒有置1的位置，記為i，則6710886437+i就是沒出現過的數。

找出100億個重復URL以及搜索詞匯topK問題 問題

有一個包含100億URL的大文件，每個URL占64B，找出重復URL；補充，找出top100搜索詞匯

常規答案

大文件通過哈希函數分配到不同機器

哈希函數將大文件拆分成小文件。

對于每一個小文件，利用哈希表遍歷，找出重復的URL，或者分給機器或拆分文件完之后，進行排序，看是否有重復的URL。

補充問題的思路也是通過哈希函數分流，對于每個小文件，簡歷詞頻哈希表，建一個大小為100的小根堆，選出每個小文件的top100.每個小文件的top100進行外排序或者接著使用小根堆，就能得到100億數據的top100.

出現兩次的數以及中位數問題 問題

有40億個無符號32位整數，最多可以使用1GB內存，找出所有出現了兩次的數；補充問題，最多使用10MB內存，找到40億個數的中位數

答案

第一個問題可以用bitmap做，申請長度為2?232bit的bitArr，2個bit表示一個數出現的詞頻。遍歷40億個數，假設出現num，將bitArr[2num]和bitArr[2num+1]設置為01，第二次出現，設置為10，第三次，設置為11。以后再遇到11的，就不做處理。遍歷完成后，再遍歷一次，若發現bitArr[2num]和bitArr[2num+1]是10，則num是出現了兩次的數。

第二個問題，分區間討論。長度為2MB的unsigned int數組占用8MB，將區間數目定位232/2M，取整為2148個區間，第0區間0~2M-1，第i區間2Mi~2M（i+1）-1

申請一個長度為2148的unsigned int整數數組arr[0..2147],arr[i]表示i區間有多少個數，arr占用內存小于10MB。遍歷40億個數，當前數num為num，落在區間(num/2M)，對應arr[num/2M]++。累加統計每個區間的累計數目，就能找到40億個數的中位數。例如0~K-1區間數目個數為19.998億，加上第K個區間就超過了20億，說要中位數一定在K區間中，并且一定是第K區間的第0.002億個數。

接著申請長度2M的unsigned int數組countArr[0..2M-1]，占用8MB。遍歷40億個數，只關心第K區間的數numi，countArr[numi-K*2M]++。統計完之后在第K區間找地0.002億個數字即可。

一致性哈希

分布式數據庫集群緩存，例如memcached，將數據的id通過哈希函數轉換為key，假設有N個機器，計算key%N，得到及其所屬編號，增刪改查都在這臺機器上。一致性哈希能在機器擴容（N發生變化），使得不用重新計算一遍key%N

三臺機器處于哈希環，id通過哈希映射為key，在哈希環中順時針找距離最近的機器。

機器較少的時候可能會出現負載不均衡，如圖所示：

答案

引入虛擬節點，增加結點數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69607.html

相關文章

  • 數據結構大總結（鏈表篇）

    摘要：實際中更多是作為其他數據結構的子結構，如哈希桶圖的鄰接表等等。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。 文章目錄 一.算法的時間復雜度和空間復雜度1.算法...

    不知名網友 評論0 收藏0

  • 七道常見的Redis面試題分享

    摘要：綜合上述缺點，小明痛定思痛，提出了經營方式二。當客戶下單，小明按送達地點標注好，依次放在一個地方。因此，有強一致性要求的數據，不能放緩存。迅速判斷出，請求所攜帶的是否合法有效。 showImg(https://segmentfault.com/img/bVbvHHL?w=1341&h=448); 絕大部分寫業務的程序員，在實際開發中使用 Redis 的時候，只會 Set Value 和...

    zhiwei 評論0 收藏0

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享 目錄： 印象中的頭條 面試背景 準備面試 ...

    tracymac7 評論0 收藏0

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享目錄：印象中的頭條面試背景準備面試頭條一面（Java+項目）頭條...

    wdzgege 評論0 收藏0

  • Java內存泄漏介紹

    摘要：本章會說明什么是內存泄漏，為什么發生，以及如何防止它們。但是，未使用的對象并不是全部未被引用，其中一些被引用這是內存泄漏的來源。注意集合類，如等，因為它們是發現內存泄漏的常見地方。如果一個類管理自己的內存，程序應該對內存泄漏保持警惕。 內存管理是Java最重要的優勢之一，你只需創建對象，Java垃圾收集器會自動負責分配和釋放內存。但是，情況并不那么簡單，因為在Java應用程序中經常發生...

    nanfeiyan 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<