【面經】将 95% 求職者拒之門外的BAT大資料面試題-附解題方法（文末有福利）

題目概覽

1. 如何從大量的 URL 中找出相同的 URL？（百度）
2. 如何按照 query 的頻度排序？（百度）
3. 如何統計不同電話号碼的個數？（百度）
4. 如何從 5 億個數中找出中位數？（百度）
5. 如何從大量資料中找出高頻詞？（百度）
6. 如何找出某一天通路百度網站最多的 IP？（百度）
7. 如何在大量的資料中找出不重複的整數？（百度）
8. 如何在大量的資料中判斷一個數是否存在？（騰訊）
9. 如何查詢最熱門的查詢串？（騰訊）
10. 如何找出排名前 500 的數？（騰訊）1、如何從大量的 URL 中找出相同的 URL？

題目分析

下面依次對以下題目進行解題思路分析：

1、如何從大量的 URL 中找出相同的 URL？

題目描述

給定 a、b 兩個檔案，各存放 50 億個 URL，每個 URL 各占 64B，記憶體限制是 4G。請找出 a、b 兩個檔案共同的 URL。

解答思路

每個 URL 占 64B，那麼 50 億個 URL占用的空間大小約為 320GB。

5,000,000,000 * 64B ≈ 5GB * 64 = 320GB

由于記憶體大小隻有 4G，是以，我們不可能一次性把所有 URL 加載到記憶體中處理。對于這種類型的題目，一般采用分治政策，即：把一個檔案中的 URL 按照某個特征劃分為多個小檔案，使得每個小檔案大小不超過 4G，這樣就可以把這個小檔案讀到記憶體中進行處理了。

思路如下：

首先周遊檔案 a，對周遊到的 URL 求 hash(URL) % 1000，根據計算結果把周遊到的 URL 存儲到 a0, a1, a2, …, a999，這樣每個大小約為 300MB。使用同樣的方法周遊檔案 b，把檔案 b 中的 URL 分别存儲到檔案 b0, b1, b2, …, b999 中。這樣處理過後，所有可能相同的 URL 都在對應的小檔案中，即 a0 對應 b0, …, a999 對應 b999，不對應的小檔案不可能有相同的 URL。那麼接下來，我們隻需要求出這 1000 對小檔案中相同的 URL 就好了。

接着周遊 ai( i∈[0,999])，把 URL 存儲到一個 HashSet 集合中。然後周遊 bi 中每個 URL，看在 HashSet 集合中是否存在，若存在，說明這就是共同的 URL，可以把這個 URL 儲存到一個單獨的檔案中。

方法總結

分而治之，進行哈希取餘；

對每個子檔案進行 HashSet 統計。

2、如何按照 query 的頻度排序？（百度）

有 10 個檔案，每個檔案大小為 1G，每個檔案的每一行存放的都是使用者的 query，每個檔案的 query 都可能重複。要求按照 query 的頻度排序。

如果 query 的重複度比較大，可以考慮一次性把所有 query 讀入記憶體中處理；如果 query 的重複率不高，那麼可用記憶體不足以容納所有的 query，這時候就需要采用分治法或其他的方法來解決。

方法一：HashMap 法

如果 query 重複率高，說明不同 query 總數比較小，可以考慮把所有的 query 都加載到記憶體中的 HashMap 中。接着就可以按照 query 出現的次數進行排序。

方法二：分治法

分治法需要根據資料量大小以及可用記憶體的大小來确定問題劃分的規模。對于這道題，可以順序周遊 10 個檔案中的 query，通過 Hash 函數 hash(query) % 10 把這些 query 劃分到 10 個小檔案中。之後對每個小檔案使用 HashMap 統計 query 出現次數，根據次數排序并寫入到零外一個單獨檔案中。

接着對所有檔案按照 query 的次數進行排序，這裡可以使用歸并排序（由于無法把所有 query 都讀入記憶體，是以需要使用外排序）。

記憶體若夠，直接讀入進行排序；

記憶體不夠，先劃分為小檔案，小檔案排好序後，整理使用外排序進行歸并。

3、如何統計不同電話号碼的個數？（百度）

已知某個檔案内包含一些電話号碼，每個号碼為 8 位數字，統計不同号碼的個數。

這道題本質還是求解資料重複的問題，對于這類問題，一般首先考慮位圖法。

對于本題，8 位電話号碼可以表示的号碼個數為 108 個，即 1 億個。我們每個号碼用一個 bit 來表示，則總共需要 1 億個 bit，記憶體占用約 100M。

申請一個位圖數組，長度為 1 億，初始化為 0。然後周遊所有電話号碼，把号碼對應的位圖中的位置置為 1。周遊完成後，如果 bit 為 1，則表示這個電話号碼在檔案中存在，否則不存在。bit 值為 1 的數量即為 不同電話号碼的個數。

求解資料重複問題，記得考慮位圖法。

4、如何從 5 億個數中找出中位數？（百度）

從 5 億個數中找出中位數。資料排序後，位置在最中間的數就是中位數。當樣本數為奇數時，中位數為 第 (N+1)/2 個數；當樣本數為偶數時，中位數為 第 N/2 個數與第 1+N/2 個數的均值。

如果這道題沒有記憶體大小限制，則可以把所有數讀到記憶體中排序後找出中位數。但是最好的排序算法的時間複雜度都為 O(NlogN)。這裡使用其他方法。

方法一：雙堆法

維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中最大的數小于等于小頂堆中最小的數；保證這兩個堆中的元素個數的差不超過 1。

若資料總數為偶數，當這兩個堆建好之後，中位數就是這兩個堆頂元素的平均值。當資料總數為奇數時，根據兩個堆的大小，中位數一定在資料多的堆的堆頂。

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        minHeap = new PriorityQueue<>(Integer::compareTo);
    }
    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() > num) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        if (size1 - size2 > 1) {
            minHeap.offer(maxHeap.poll());
        } else if (size2 - size1 > 1) {
            maxHeap.offer(minHeap.poll());
        }
    }
    public double findMedian() {
        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        return size1 == size2 
            ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
            : (size1 > size2 ? maxHeap.peek() : minHeap.peek());
    }
}      

以上這種方法，需要把所有資料都加載到記憶體中。當資料量很大時，就不能這樣了，是以，這種方法适用于資料量較小的情況。5 億個數，每個數字占用 4B，總共需要 2G 記憶體。如果可用記憶體不足 2G，就不能使用這種方法了，下面介紹另一種方法。

分治法的思想是把一個大的問題逐漸轉換為規模較小的問題來求解。

對于這道題，順序讀取這 5 億個數字，對于讀取到的數字 num，如果它對應的二進制中最高位為1，則把這個數字寫到 f1 中，否則寫入 f0 中。通過這一步，可以把這 5 億個數劃分為兩部分，而且 f0 中的數都大于 f1 中的數（最高位是符号位）。

劃分之後，可以非常容易地知道中位數是在 f0 還是 f1 中。假設 f1 中有 1 億個數，那麼中位數一定在 f0 中，且是在 f0 中，從小到大排列的第 1.5 億個數與它後面的一個數的平均值。

提示，5 億數的中位數是第 2.5 億與右邊相鄰一個數求平均值。若 f1 有一億個數，那麼中位數就是 f0 中從第 1.5 億個數開始的兩個數求得的平均值。

對于 f0 可以用次高位的二進制繼續将檔案一分為二，如此劃分下去，直到劃分後的檔案可以被加載到記憶體中，把資料加載到記憶體中以後直接排序，找出中位數。

注意，當資料總數為偶數，如果劃分後兩個檔案中的資料有相同個數，那麼中位數就是資料較小的檔案中的最大值與資料較大的檔案中的最小值的平均值。

分治法，真香！

5、如何從大量資料中找出高頻詞？（百度）

有一個 1GB 大小的檔案，檔案裡每一行是一個詞，每個詞的大小不超過 16B，記憶體大小限制是 1MB，要求傳回頻數最高的 100 個詞(Top 100)。

由于記憶體限制，我們依然無法直接将大檔案的所有詞一次讀到記憶體中。是以，同樣可以采用分治政策，把一個大檔案分解成多個小檔案，保證每個檔案的大小小于 1MB，進而直接将單個小檔案讀取到記憶體中進行處理。

首先周遊大檔案，對周遊到的每個詞x，執行 hash(x) % 5000，将結果為 i 的詞存放到檔案 ai 中。周遊結束後，我們可以得到 5000 個小檔案。每個小檔案的大小為 200KB 左右。如果有的小檔案大小仍然超過 1MB，則采用同樣的方式繼續進行分解。

接着統計每個小檔案中出現頻數最高的 100 個詞。最簡單的方式是使用 HashMap 來實作。其中 key 為詞，value 為該詞出現的頻率。具體方法是：對于周遊到的詞 x，如果在 map 中不存在，則執行 map.put(x, 1)；若存在，則執行 map.put(x, map.get(x)+1)，将該詞頻數加 1。

上面我們統計了每個小檔案單詞出現的頻數。接下來，我們可以通過維護一個小頂堆來找出所有詞中出現頻數最高的 100 個。具體方法是：依次周遊每個小檔案，建構一個小頂堆，堆大小為 100。如果周遊到的詞的出現次數大于堆頂詞的出現次數，則用新詞替換堆頂的詞，然後重新調整為小頂堆，周遊結束後，小頂堆上的詞就是出現頻數最高的 100 個詞。

使用 HashMap 統計頻數；

求解最大的 TopN 個，用小頂堆；求解最小的 TopN 個，用大頂堆。

6、如何找出某一天通路百度網站最多的 IP？（百度）

現有海量日志資料儲存在一個超大檔案中，該檔案無法直接讀入記憶體，要求從中提取某天通路百度次數最多的那個 IP。

這道題隻關心某一天通路百度最多的 IP，是以，可以首先對檔案進行一次周遊，把這一天通路百度 IP 的相關資訊記錄到一個單獨的大檔案中。接下來采用的方法與上一題一樣，大緻就是先對 IP 進行哈希映射，接着使用 HashMap 統計重複 IP 的次數，最後計算出重複次數最多的 IP。

注：這裡隻需要找出出現次數最多的 IP，可以不必使用堆，直接用一個變量 max 即可。

7、如何在大量的資料中找出不重複的整數？（百度）

在 2.5 億個整數中找出不重複的整數。注意：記憶體不足以容納這 2.5 億個整數。

方法一：分治法

與前面的題目方法類似，先将 2.5 億個數劃分到多個小檔案，用 HashSet/HashMap 找出每個小檔案中不重複的整數，再合并每個子結果，即為最終結果。

方法二：位圖法

位圖，就是用一個或多個 bit 來标記某個元素對應的值，而鍵就是該元素。采用位作為機關來存儲資料，可以大大節省存儲空間。

位圖通過使用位數組來表示某些元素是否存在。它可以用于快速查找，判重，排序等。不是很清楚？我先舉個小例子。

假設我們要對 [0,7] 中的 5 個元素 (6, 4, 2, 1, 5) 進行排序，可以采用位圖法。0~7 範圍總共有 8 個數，隻需要 8bit，即 1 個位元組。首先将每個位都置 0：

0 0 0 0 0 0 0 0      

然後周遊 5 個元素，首先遇到 6，那麼将下标為 6 的位的 0 置為 1；接着遇到 4，把下标為 4 的位 的 0 置為 1：

0 0 0 0 1 0 1 0      

依次周遊，結束後，位數組是這樣的：

0 1 1 0 1 1 1 0      

每個為 1 的位，它的下标都表示了一個數：

for i in range(8):
    if bits[i] == 1:
        print(i)      

這樣我們其實就已經實作了排序。

對于整數相關的算法的求解，位圖法是一種非常實用的算法。假設 int 整數占用 4B，即 32bit，那麼我們可以表示的整數的個數為 232。

那麼對于這道題，我們用 2 個 bit 來表示各個數字的狀态：

00 表示這個數字沒出現過；

01 表示這個數字出現過一次（即為題目所找的不重複整數）；

10 表示這個數字出現了多次。

那麼這 232 個整數，總共所需記憶體為 232*2b=1GB。是以，當可用記憶體超過 1GB 時，可以采用位圖法。假設記憶體滿足位圖法需求，進行下面的操作：

周遊 2.5 億個整數，檢視位圖中對應的位，如果是 00，則變為 01，如果是 01 則變為 10，如果是 10 則保持不變。周遊結束後，檢視位圖，把對應位是 01 的整數輸出即可。

判斷數字是否重複的問題，位圖法是一種非常高效的方法。

8、如何在大量的資料中判斷一個數是否存在？（騰訊）

給定 40 億個不重複的沒排過序的 unsigned int 型整數，然後再給定一個數，如何快速判斷這個數是否在這 40 億個整數當中？

依然可以用分治法解決，方法與前面類似，就不再次贅述了。

40 億個不重複整數，我們用 40 億個 bit 來表示，初始位均為 0，那麼總共需要記憶體：4,000,000,000b≈512M。

我們讀取這 40 億個整數，将對應的 bit 設定為 1。接着讀取要查詢的數，檢視相應位是否為 1，如果為 1 表示存在，如果為 0 表示不存在。

判斷數字是否存在、判斷數字是否重複的問題，位圖法是一種非常高效的方法。

9、如何查詢最熱門的查詢串？（騰訊）

搜尋引擎會通過日志檔案把使用者每次檢索使用的所有查詢串都記錄下來，每個查詢床的長度不超過 255 位元組。

假設目前有 1000w 個記錄（這些查詢串的重複度比較高，雖然總數是 1000w，但如果除去重複後，則不超過 300w 個）。請統計最熱門的 10 個查詢串，要求使用的記憶體不能超過 1G。（一個查詢串的重複度越高，說明查詢它的使用者越多，也就越熱門。）

每個查詢串最長為 255B，1000w 個串需要占用 約 2.55G 記憶體，是以，我們無法将所有字元串全部讀入到記憶體中處理。

分治法依然是一個非常實用的方法。

劃分為多個小檔案，保證單個小檔案中的字元串能被直接加載到記憶體中處理，然後求出每個檔案中出現次數最多的 10 個字元串；最後通過一個小頂堆統計出所有檔案中出現最多的 10 個字元串。

方法可行，但不是最好，下面介紹其他方法。

方法二：HashMap 法

雖然字元串總數比較多，但去重後不超過 300w，是以，可以考慮把所有字元串及出現次數儲存在一個 HashMap 中，所占用的空間為 300w*(255+4)≈777M（其中，4表示整數占用的4個位元組）。由此可見，1G 的記憶體空間完全夠用。

首先，周遊字元串，若不在 map 中，直接存入 map，value 記為 1；若在 map 中，則把對應的 value 加 1，這一步時間複雜度 O(N)。

接着周遊 map，建構一個 10 個元素的小頂堆，若周遊到的字元串的出現次數大于堆頂字元串的出現次數，則進行替換，并将堆調整為小頂堆。

周遊結束後，堆中 10 個字元串就是出現次數最多的字元串。這一步時間複雜度 O(Nlog10)。

方法三：字首樹法

方法二使用了 HashMap 來統計次數，當這些字元串有大量相同字首時，可以考慮使用字首樹來統計字元串出現的次數，樹的結點儲存字元串出現次數，0 表示沒有出現。

在周遊字元串時，在字首樹中查找，如果找到，則把結點中儲存的字元串次數加 1，否則為這個字元串建構新結點，建構完成後把葉子結點中字元串的出現次數置為 1。

最後依然使用小頂堆來對字元串的出現次數進行排序。

字首樹經常被用來統計字元串的出現次數。它的另外一個大的用途是字元串查找，判斷是否有重複的字元串等。

10如何找出排名前 500 的數？（騰訊）

有 20 個數組，每個數組有 500 個元素，并且有序排列。如何在這 20*500 個數中找出前 500 的數？

對于 TopK 問題，最常用的方法是使用堆排序。對本題而言，假設數組降序排列，可以采用以下方法：

首先建立大頂堆，堆的大小為數組的個數，即為 20，把每個數組最大的值存到堆中。

接着删除堆頂元素，儲存到另一個大小為 500 的數組中，然後向大頂堆插入删除的元素所在數組的下一個元素。

重複上面的步驟，直到删除完第 500 個元素，也即找出了最大的前 500 個數。

為了在堆中取出一個資料後，能知道它是從哪個數組中取出的，進而可以從這個數組中取下一個值，可以把數組的指針存放到堆中，對這個指針提供比較大小的方法。

import lombok.Data;
import java.util.Arrays;
import java.util.PriorityQueue;
@Data
public class DataWithSource implements Comparable<DataWithSource> {
    /**
     * 數值
     */
    private int value;
    /**
     * 記錄數值來源的數組
     */
    private int source;
    /**
     * 記錄數值在數組中的索引
     */
    private int index;
    public DataWithSource(int value, int source, int index) {
        this.value = value;
        this.source = source;
        this.index = index;
    }
    /**
     *
     * 由于 PriorityQueue 使用小頂堆來實作，這裡通過修改
     * 兩個整數的比較邏輯來讓 PriorityQueue 變成大頂堆
     */
    @Override
    public int compareTo(DataWithSource o) {
        return Integer.compare(o.getValue(), this.value);
    }
}
class Test {
    public static int[] getTop(int[][] data) {
        int rowSize = data.length;
        int columnSize = data[0].length;
        // 建立一個columnSize大小的數組，存放結果
        int[] result = new int[columnSize];
        PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
        for (int i = 0; i < rowSize; ++i) {
            // 将每個數組的最大一個元素放入堆中
            DataWithSource d = new DataWithSource(data[i][0], i, 0);
            maxHeap.add(d);
        }
        int num = 0;
        while (num < columnSize) {
            // 删除堆頂元素
            DataWithSource d = maxHeap.poll();
            result[num++] = d.getValue();
            if (num >= columnSize) {
                break;
            }
            d.setValue(data[d.getSource()][d.getIndex() + 1]);
            d.setIndex(d.getIndex() + 1);
            maxHeap.add(d);
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] data = {
                {29, 17, 14, 2, 1},
                {19, 17, 16, 15, 6},
                {30, 25, 20, 14, 5},
        };
        int[] top = getTop(data);
        System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
    }
}