字節(jié)終面:兩個文件的公共url怎么找?
大家好，我是道哥。今天，我們來看一道非常經(jīng)典的面試題目。
在字節(jié)跳動的終面中，居然遇到這個題目，好親切。題目如下：
A文件有32億個url鏈接，B文件有64億個url鏈接，求A和B中的公共url鏈接。
一. 初步思考
一些朋友可能覺得，這個問題很簡單啊，把A文件和B文件同時加載到內(nèi)存中，然后進行循環(huán)查找比較，貌似萬事大吉。
為了便于理解原問題，我用圖解的方式來進行。設A文件有5個美女，居于上面一行；B文件有5個美女，居于下面一行。
那么，怎么找出上下兩行的公共部分呢？且看最直觀的思路，那就一個個地找唄。
第1步：
以紫衫龍王為例，發(fā)現(xiàn)下面一行沒有紫衫龍王，所以紫衫龍王不是上下的公共部分，如圖：
第2步：
以黃蓉為例，發(fā)現(xiàn)下面一行有黃蓉，所以黃蓉是上下的公共部分，如圖：
第3步：
以穆念慈為例，發(fā)現(xiàn)下面一行沒有穆念慈，所以穆念慈不是上下的公共部分，如圖：
第4步：
以白發(fā)魔女為例，發(fā)現(xiàn)下面一行有白發(fā)魔女，所以白發(fā)魔女是上下的公共部分，如圖：
第5步：
以趙敏為例，發(fā)現(xiàn)下面一行有趙敏，所以趙敏是上下的公共部分，如圖：
我們看到，整個過程進行了25次比較。顯然，上下兩行的公共部分是：黃蓉、趙敏、白發(fā)魔女。
如果A有m個元素，B有n個元素，則時間復雜度為O(m*n)，顯然，無法通過字節(jié)跳動的面試。
二. 進階思考
從時間復雜度上來講，上面的方法肯定不是最優(yōu)的，這里的問題在哪里呢？問題還是出在查找的思路上。
我們以紫衫龍王的查找為例，使用遍歷查找的思路是很糟糕的。從下圖可以看出，需要查找5次才有結果：
回顧一下查找算法，比遍歷查找更快的是二分查找，比二分查找更快的是哈希查找。
來看看使用哈希表進行查找的圖示，哈希查找的時間復雜度為O(1)，不需要比較5次：
貌似萬事大吉了，但依然無法通過字節(jié)跳動的面試，這又是為什么呢？貓膩在哪里？
醒醒，快醒醒，這明顯是一道海量數(shù)據(jù)問題，內(nèi)存容納不下，所以必須想其他的方法。
三. 終極思考
由于是海量數(shù)據(jù)問題，內(nèi)存容納不下，那怎么辦呢？可以考慮使用分治的思想，說白了，就是大問題化小，小問題化了。
還是以上述的美女為例，我們可以考慮對這些美女進行分類。具體的分類標準有很多，比如，可以考慮以名字長度來分。
原來的圖示如下：
根據(jù)名字長度劃分后圖示如下：
顯而易見，這就實現(xiàn)了化大為小，在化大為小之后，內(nèi)存足夠容納得下，不用擔心了。
很容易發(fā)現(xiàn)，上下兩行的公共部分分別是：黃蓉、趙敏、白發(fā)魔女。問題得到解決啦。
值得注意的是，我們以名字長度為4的房間為例，針對紫衫龍王，仍選擇用哈希查找。
四. 破解原題
我們一起來回顧下原題：
A文件有32億個url鏈接，B文件有64億個url鏈接，求A和B中的公共url鏈接。
顯然，內(nèi)存容納不下這么多數(shù)據(jù)，因此需要采用分割的方法對A和B兩個文件中的url進行分類。
怎么分類呢？我們當然可以根據(jù)url的長度進行分類，分成不同的比較組，比如：
這樣就能解決問題了。但是，還有一個問題，這種劃分合理嗎？是否存在某個長度的url有很多呢？
會的，一定會的。如果某個長度的url很多，會導致小文件也很大，導致內(nèi)存容納不下，那怎么辦？
可以考慮采取哈希的思想，具體來說就是對每個url求md5值，然后按照md5值的首字母來分割：
把大文件按照一定的規(guī)則切割成小文件后，內(nèi)存容納不下的問題解決了。按照上述分法之后，如果文件還是太大，那怎么辦呢？
很簡單，可以考慮多分割一些，比如按照md5后的前兩個字母來分割。顯然，一個大文件可以分為256個小文件，如下所示：
| 文件分割 | md5后前兩個字母 |
| 小文件1 | aa |
| 小文件2 | ab |
| 小文件3 | ac |
| 小文件4 | ad |
| ... | ... |
| 小文件256 | zz |
總之，核心思想是：
哈希分治，把大文件切割為很多的小文件
在每一組小文件中，找出它們的共同url
表格示意圖如下：
| md5后前兩個字母 | A | VS | B |
| aa | A1文件 | VS | B1文件 |
| ab | A2文件 | VS | B2文件 |
| ac | A3文件 | VS | B3文件 |
| ad | A4文件 | VS | B4文件 |
| ... | ... | VS | ... |
| zz | A256文件 | VS | B256文件 |
道哥，CSDN前30名，曾混跡于BAT大廠。公眾號講解計算機基礎、網(wǎng)絡、數(shù)據(jù)結構、算法、C++、Java、Golang等多方面的編程知識。歡迎點擊如下名片關注道哥，感謝點贊和在看支持哦。