字節(jié)終面：兩個(gè)文件的公共URL怎么找？

往期熱門文章：

1、留在一線，逃離一線？我從上海舉家回成都的生活經(jīng)歷告訴你
2、公司規(guī)定所有接口都用 POST請(qǐng)求，這是為什么？
3、我被這個(gè)瀏覽了 746000 次的問題驚住了！
4、騰訊三面：40億個(gè)QQ號(hào)碼如何去重？
5、自從用完Gradle后，有點(diǎn)嫌棄Maven了！速度賊快！

今天，我們來看一道非常經(jīng)典的面試題目。

在字節(jié)跳動(dòng)的終面中，居然遇到這個(gè)題目，好親切。題目如下：

A文件有32億個(gè)url鏈接，B文件有64億個(gè)url鏈接，求A和B中的公共url鏈接。

一. 初步思考

一些朋友可能覺得，這個(gè)問題很簡(jiǎn)單啊，把A文件和B文件同時(shí)加載到內(nèi)存中，然后進(jìn)行循環(huán)查找比較，貌似萬事大吉。

為了便于理解原問題，我用圖解的方式來進(jìn)行。設(shè)A文件有5個(gè)美女，居于上面一行；B文件有5個(gè)美女，居于下面一行。

那么，怎么找出上下兩行的公共部分呢？且看最直觀的思路，那就一個(gè)個(gè)地找唄。

第1步：

以紫衫龍王為例，發(fā)現(xiàn)下面一行沒有紫衫龍王，所以紫衫龍王不是上下的公共部分，如圖：

第2步：

以黃蓉為例，發(fā)現(xiàn)下面一行有黃蓉，所以黃蓉是上下的公共部分，如圖：

第3步：

以穆念慈為例，發(fā)現(xiàn)下面一行沒有穆念慈，所以穆念慈不是上下的公共部分，如圖：

第4步：

以白發(fā)魔女為例，發(fā)現(xiàn)下面一行有白發(fā)魔女，所以白發(fā)魔女是上下的公共部分，如圖：

第5步：

以趙敏為例，發(fā)現(xiàn)下面一行有趙敏，所以趙敏是上下的公共部分，如圖：

我們看到，整個(gè)過程進(jìn)行了25次比較。顯然，上下兩行的公共部分是：黃蓉、趙敏、白發(fā)魔女。

如果A有m個(gè)元素，B有n個(gè)元素，則時(shí)間復(fù)雜度為O(m*n)，顯然，無法通過字節(jié)跳動(dòng)的面試。

二. 進(jìn)階思考

從時(shí)間復(fù)雜度上來講，上面的方法肯定不是最優(yōu)的，這里的問題在哪里呢？問題還是出在查找的思路上。

我們以紫衫龍王的查找為例，使用遍歷查找的思路是很糟糕的。從下圖可以看出，需要查找5次才有結(jié)果：

回顧一下查找算法，比遍歷查找更快的是二分查找，比二分查找更快的是哈希查找。

來看看使用哈希表進(jìn)行查找的圖示，哈希查找的時(shí)間復(fù)雜度為O(1)，不需要比較5次：

貌似萬事大吉了，但依然無法通過字節(jié)跳動(dòng)的面試，這又是為什么呢？貓膩在哪里？

醒醒，快醒醒，這明顯是一道海量數(shù)據(jù)問題，內(nèi)存容納不下，所以必須想其他的方法。

三. 終極思考

由于是海量數(shù)據(jù)問題，內(nèi)存容納不下，那怎么辦呢？可以考慮使用分治的思想，說白了，就是大問題化小，小問題化了。

還是以上述的美女為例，我們可以考慮對(duì)這些美女進(jìn)行分類。具體的分類標(biāo)準(zhǔn)有很多，比如，可以考慮以名字長(zhǎng)度來分。

原來的圖示如下：

根據(jù)名字長(zhǎng)度劃分后圖示如下：

顯而易見，這就實(shí)現(xiàn)了化大為小，在化大為小之后，內(nèi)存足夠容納得下，不用擔(dān)心了。

很容易發(fā)現(xiàn)，上下兩行的公共部分分別是：黃蓉、趙敏、白發(fā)魔女。問題得到解決啦。

值得注意的是，我們以名字長(zhǎng)度為4的房間為例，針對(duì)紫衫龍王，仍選擇用哈希查找。

四. 破解原題

我們一起來回顧下原題：

A文件有32億個(gè)url鏈接，B文件有64億個(gè)url鏈接，求A和B中的公共url鏈接。

顯然，內(nèi)存容納不下這么多數(shù)據(jù)，因此需要采用分割的方法對(duì)A和B兩個(gè)文件中的url進(jìn)行分類。

怎么分類呢？我們當(dāng)然可以根據(jù)url的長(zhǎng)度進(jìn)行分類，分成不同的比較組，比如：

這樣就能解決問題了。但是，還有一個(gè)問題，這種劃分合理嗎？是否存在某個(gè)長(zhǎng)度的url有很多呢？

會(huì)的，一定會(huì)的。如果某個(gè)長(zhǎng)度的url很多，會(huì)導(dǎo)致小文件也很大，導(dǎo)致內(nèi)存容納不下，那怎么辦？

可以考慮采取哈希的思想，具體來說就是對(duì)每個(gè)url求md5值，然后按照md5值的首字母來分割：

把大文件按照一定的規(guī)則切割成小文件后，內(nèi)存容納不下的問題解決了。按照上述分法之后，如果文件還是太大，那怎么辦呢？

很簡(jiǎn)單，可以考慮多分割一些，比如按照md5后的前兩個(gè)字母來分割。顯然，一個(gè)大文件可以分為256個(gè)小文件，如下所示：

文件分割	md5后前兩個(gè)字母
小文件1	aa
小文件2	ab
小文件3	ac
小文件4	ad
...	...
小文件256	zz

總之，核心思想是：

• 哈希分治，把大文件切割為很多的小文件

• 在每一組小文件中，找出它們的共同url

表格示意圖如下：

md5后前兩個(gè)字母	A	VS	B
aa	A1文件	VS	B1文件
ab	A2文件	VS	B2文件
ac	A3文件	VS	B3文件
ad	A4文件	VS	B4文件
...	...	VS	...
zz	A256文件	VS	B256文件

哈希分治，化大為小，是一種重要的思想。我們也會(huì)一步一個(gè)腳印，爭(zhēng)取每篇文章講清講透一件事，也希望大家閱讀后有所收獲，心情愉快。

往期熱門文章：
1、《歷史文章分類導(dǎo)讀列表！精選優(yōu)秀博文都在這里了！》
2、為什么國(guó)內(nèi) 996 干不過國(guó)外的 955 呢？
3、在部隊(duì)當(dāng)程序員是什么體驗(yàn)？
4、神級(jí)程序員都在用什么工具？
5、是時(shí)候扔掉 Postman 了，Apifox 真香！
6、這些年我用過的 6個(gè)API 接口文檔平臺(tái)，真的好用
7、Redis 實(shí)現(xiàn)限流的三種簡(jiǎn)單方式
8、9個(gè)GVP國(guó)產(chǎn)Java開源項(xiàng)目！是真滴哇塞
9、阿里領(lǐng)導(dǎo)：手下兩個(gè)應(yīng)屆生，一個(gè)踏實(shí)喜歡加班，一個(gè)技術(shù)強(qiáng)挑活，怎么選？
10、這就是最適合程序員的云筆記？