字节终面:两个文件的公共url怎么找?

bigsai

共 1796字,需浏览 4分钟

 ·

2021-08-24 22:45

大家好,我是道哥。今天,我们来看一道非常经典的面试题目。

在字节跳动的终面中,居然遇到这个题目,好亲切。目如下:

A文件有32亿个url链接,B文件有64亿个url链接,求A和B中的公共url链接。

f5e65c6b7801fa70ed84a7602b5d3f42.webp


一. 初步思考

一些朋友可能觉得,这个问题很简单啊,把A文件和B文件同时加载到内存中,然后进行循环查找比较,貌似万事大吉。

为了便于理解原问题,我用图解的方式来进行。设A文件有5个美女,居于上面一行;B文件有5个美女,居于下面一行。

那么,怎么找出上下两行的公共部分呢?且看最直观的思路,那就一个个地找呗。

第1步:

以紫衫龙王为例,发现下面一行没有紫衫龙王,所以紫衫龙王不是上下的公共部分,如图:

5bb40ae38e70d5e53d20d3cfe7b7b0ae.webp


第2步:

以黄蓉为例,发现下面一行有黄蓉,所以黄蓉是上下的公共部分,如图:

fcad47884b30c80b9445fd19428312a9.webp


第3步:

以穆念慈为例,发现下面一行没有穆念慈,所以穆念慈不是上下的公共部分,如图:

4b316a2640069b2244857a4f1529fa5c.webp


第4步:

以白发魔女为例,发现下面一行有白发魔女,所以白发魔女是上下的公共部分,如图:

f1985968aae4e6abadb67b44ace07aeb.webp


第5步:

以赵敏为例,发现下面一行有赵敏,所以赵敏是上下的公共部分,如图:

828c0391cb2008cb073229c23b732c11.webp


我们看到,整个过程进行了25次比较。显然,上下两行的公共部分是:黄蓉、赵敏、白发魔女

如果A有m个元素,B有n个元素,则时间复杂度为O(m*n),显然,无法通过字节跳动的面试。


二. 进阶思考

从时间复杂度上来讲,上面的方法肯定不是最优的,这里的问题在哪里呢?问题还是出在查找的思路上。

我们以紫衫龙王的查找为例,使用遍历查找的思路是很糟糕的。从下图可以看出,需要查找5次才有结果:

5bb40ae38e70d5e53d20d3cfe7b7b0ae.webp


回顾一下查找算法,比遍历查找更快的是二分查找,比二分查找更快的是哈希查找。

来看看使用哈希表进行查找的图示,哈希查找的时间复杂度为O(1),不需要比较5次:

c2cbe3469434bb01ed91db680dc1bf53.webp


貌似万事大吉了,但依然无法通过字节跳动的面试,这又是为什么呢?猫腻在哪里?

醒醒,快醒醒,这明显是一道海量数据问题,内存容纳不下,所以必须想其他的方法。


三. 终极思考

由于是海量数据问题,内存容纳不下,那怎么办呢?可以考虑使用分治的思想,说白了,就是大问题化小,小问题化了。

还是以上述的美女为例,我们可以考虑对这些美女进行分类。具体的分类标准有很多,比如,可以考虑以名字长度来分。

原来的图示如下:

f5e65c6b7801fa70ed84a7602b5d3f42.webp


根据名字长度划分后图示如下:

d3d8d01afcc3940d5f4e86899c90cd7c.webp


显而易见,这就实现了化大为小,在化大为小之后,内存足够容纳得下,不用担心了。

很容易发现,上下两行的公共部分分别是:黄蓉、赵敏、白发魔女。问题得到解决啦。

值得注意的是,我们以名字长度为4的房间为例,针对紫衫龙王,仍选择用哈希查找。


四. 破解原题

我们一起来回顾下原题:

A文件有32亿个url链接,B文件有64亿个url链接,求A和B中的公共url链接。

显然,内存容纳不下这么多数据,因此需要采用分割的方法对A和B两个文件中的url进行分类。

怎么分类呢?我们当然可以根据url的长度进行分类,分成不同的比较组,比如:

d9341b5c6ce485a3d3ff9a7db175c428.webp


这样就能解决问题了。但是,还有一个问题,这种划分合理吗?是否存在某个长度的url有很多呢?

会的,一定会的。如果某个长度的url很多,会导致小文件也很大,导致内存容纳不下,那怎么办?

可以考虑采取哈希的思想,具体来说就是对每个url求md5值,然后按照md5值的首字母来分割:

9ff05bbbe931738bc76d615222c0cecd.webp


把大文件按照一定的规则切割成小文件后,内存容纳不下的问题解决了。按照上述分法之后,如果文件还是太大,那怎么办呢?

很简单,可以考虑多分割一些,比如按照md5后的前两个字母来分割。显然,一个大文件可以分为256个小文件,如下所示:

文件分割md5后前两个字母
小文件1aa
小文件2
ab
小文件3
ac
小文件4
ad
...
...
小文件256
zz


总之,核心思想是:

  • 哈希分治,把大文件切割为很多的小文件

  • 在每一组小文件中,找出它们的共同url

表格示意图如下:

md5后前两个字母A
VS
B
aa
A1文件
VSB1文件
ab
A2文件VSB2文件
acA3文件VSB3文件
ad
A4文件VSB4文件
...
...VS...
zz
A256文件VSB256文件


哈希分治,化大为小,是一种重要的思想。我们也会一步一个脚印,争取每篇文章讲清讲透一件事,也希望大家阅读后有所收获,心情愉快。7c632ab4b6450d4c611725c1eb45c40d.webp道哥,CSDN前30名,曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。欢迎点击如下名片关注道哥,感谢点赞和在看支持哦。
浏览 26
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报