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

Java后端技术

共 2171字,需浏览 5分钟

 · 2021-12-15

往期热门文章:

1、留在一线,逃离一线?我从上海举家回成都的生活经历告诉你

2、公司规定所有接口都用 POST请求,这是为什么?

3、我被这个浏览了 746000 次的问题惊住了!

4、腾讯三面:40亿个QQ号码如何去重?

5、自从用完Gradle后,有点嫌弃Maven了!速度贼快!

今天,我们来看一道非常经典的面试题目。

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

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


一. 初步思考

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

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

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

第1步:

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


第2步:

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


第3步:

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


第4步:

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


第5步:

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


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

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


二. 进阶思考

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

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


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

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


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

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


三. 终极思考

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

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

原来的图示如下:


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


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

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

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


四. 破解原题

我们一起来回顾下原题:

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

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

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


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

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

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


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

很简单,可以考虑多分割一些,比如按照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文件


哈希分治,化大为小,是一种重要的思想。我们也会一步一个脚印,争取每篇文章讲清讲透一件事,也希望大家阅读后有所收获,心情愉快。

往期热门文章:

1、历史文章分类导读列表!精选优秀博文都在这里了!》
2、为什么国内 996 干不过国外的 955 呢?
3、在部队当程序员是什么体验?
4、神级程序员都在用什么工具?
5、是时候扔掉 Postman 了,Apifox 真香!
6、这些年我用过的 6个API 接口文档平台,真的好用
7、Redis 实现限流的三种简单方式
8、9个GVP国产Java开源项目!是真滴哇塞
9、阿里领导:手下两个应届生,一个踏实喜欢加班,一个技术强挑活,怎么选?
10、这就是最适合程序员的云笔记?

浏览 4
点赞
评论
收藏
分享

手机扫一扫分享

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

手机扫一扫分享

举报