腾讯终面：求QQ交集

Love The Way You Lie 2022-09-16 06:12 145阅读 0赞

![73bd650c3a36e5b0016d8f34b784fffa.png][]

若有收获，记得分享和转发哦

![f3a8c41b7b76cd51b34e504528f914ea.png][]

今天，我们来看一道腾讯的终面题目，能否做对这道题，在很大程度上决定了能否拿到腾讯的offer，来看看：

A文件有30亿个QQ号码，B文件有40亿个QQ号码，求A文件和B文件中QQ号码的交集，内存大小限制为1GB.

## 一. 直接暴力比较 ##

最简单的方法是直接暴力比较，如下：

![f243cb3715b80f49d793b6a11c4eca2a.png][]

![97f095a32b57ab7c92688d82c6d05606.png][]

![6397c2c767faa8e902c59ff272940c2f.png][]

显然，这种方法要比较的次数是：30亿\*40亿，时间复杂度太大了，无法通过腾讯面试。

## 二. 利用hashmap ##

既然时间复杂度不符合要求，那就要反思一下暴力比较的算法了，显然，应该用哈希表，优化查找速度，如下：

![7c10ae4573bc432446956015a1c13a42.png][]

![5529a76b0e35b82a3306df91b8a99d1d.png][]

![f56a4084d664331882d8cfe2e77c032d.png][]

显然，时间复杂度大大降低，只需要遍历上面一层即可。然而，空间的占用还是太大了，1GB的内存根本无法容纳40亿个QQ号。无法通过腾讯面试。

## 三. 分治切割文件 ##

![2ab59c14da2d9409a75d187ab4addfcd.png][]

![7ef89e4fa6afed41c235ffaf02c1f8f5.png][]

![d8634256cabba16f3d5676a9f91bfd97.png][]

## 四. 利用bitmap ##

![dcae12234f11ae692b8e6b4712c86cfd.png][]

![e675fa7fdc7b0f4bc216e2bc376c5c43.png][]

这是一个unsigned char类型，可以看到，共有8位，取值范围是\[0, 255\]，如上这个unsigned char的值是255，它能标识0~7这些数字都存在。

同理，如下这个unsigned char类型的值是254，它对应的含义是：1~7这些数字存在，而数字0不存在：

![02c66fb3b6a890d71d454165b85b67ea.png][]

![c5aae314bf49a24e5ec0f598d292a748.png][]

[73bd650c3a36e5b0016d8f34b784fffa.png]: /images/20220828/710b54e8f81d48228b7bdb3267c17e90.png
[f3a8c41b7b76cd51b34e504528f914ea.png]: /images/20220828/24bdc5c214724301aa9bac5fa78fba76.png
[f243cb3715b80f49d793b6a11c4eca2a.png]: /images/20220828/ba0c13b2090b4772924a7e1806d63c22.png
[97f095a32b57ab7c92688d82c6d05606.png]: /images/20220828/fecdb430e0e045c889b26e757e1f1765.png
[6397c2c767faa8e902c59ff272940c2f.png]: /images/20220828/3b55ca631ca947188537c77890007d66.png
[7c10ae4573bc432446956015a1c13a42.png]: /images/20220828/ff3efec403134241a47133c9b9615298.png
[5529a76b0e35b82a3306df91b8a99d1d.png]: /images/20220828/77259203131940e7be55b8731c2a2aea.png
[f56a4084d664331882d8cfe2e77c032d.png]: /images/20220828/5fe143dd5d2b4b199c62671559cf35c6.png
[2ab59c14da2d9409a75d187ab4addfcd.png]: /images/20220828/64d21b5aa0ca44d38a123532828e6de8.png
[7ef89e4fa6afed41c235ffaf02c1f8f5.png]: /images/20220828/347fb456d3344b499da1ea4b3d88880a.png
[d8634256cabba16f3d5676a9f91bfd97.png]: /images/20220828/405454a244bc4687bd28f1f9b5e8ebec.png
[dcae12234f11ae692b8e6b4712c86cfd.png]: /images/20220828/d236419ceec84a10a6bb7d61c5e26135.png
[e675fa7fdc7b0f4bc216e2bc376c5c43.png]: /images/20220828/2fdfa69c4f4c47d39f350b27e58d5f0e.png
[02c66fb3b6a890d71d454165b85b67ea.png]: /images/20220828/5fc67a33457742d188aa776377e4b7fd.png
[c5aae314bf49a24e5ec0f598d292a748.png]: /images/20220828/cc2dc1b946bd4af7a751cda3484cb2bb.png