腾讯二面:20亿个QQ号码如何去重?

共 1063字,需浏览 3分钟

 ·

2021-12-09 21:22


背景

之前找工作在腾讯面试遇到了一个很有意思的面试题,当时我记得现场还没有答出来,后来回家想了一下其实也没有那么难,而且还挺有意思的,今天做个整理分享给大家,希望对你有用

题目如下

文件中有20亿个QQ号码,请设计算法对QQ号码去重,相同的QQ号码仅保留一个,内存限制1G. 这个题目的意思应该很清楚了,不过为了方便大家理解,我画了一个比较有年代感的动画,希望大家喜欢

方法一

排序去重

其实说到去重,最简单的方法就是先排序,排序之后重复的QQ号码必然在一起,保留第一个,把其余重复的去掉就行,

整个过程如下面动画虽然这样可以解决问题,排序往往复杂度都很高,所以必定不是最优解

方法二

hashmap

如果排序的复杂对太高,那么直接用hashmap吧,hashmap的复杂度为O(1),思路其实很简单,就是直接把qq号记录到hashmap中,要是php的话直接记录在数组中就可以

hashMap[123] = true
hashMap[456] = true
hashMap[123] = true
hashMap[789] = true

由于hashmap的自动去重性质,所以自动变成了:

hashMap[123] = true
hashMap[456] = true
hashMap[789] = true

很显然,只有123,456,789存在,所以这也就是去重后的结果。

可是,面试官又要问你了:实际要存20亿QQ号码,1G的内存够分配这么多空间吗?显然不行,这样回答你还是无法通过腾讯面试

方法三

bitmap

来看绝招!我们可以对hashmap进行优化,采用bitmap这种数据结构,可以顺利地同时解决时间问题和空间问题。如果对bitmap不是很熟悉,可以看看我的这两篇文章

redis中bitmap(位操作)的实际应用12306抢票算法居然被曝光了!!!居然这么简单

对bitmap有了大概的了解之后,我们直接把存在的qq号码对应的位置标记为1即可,下次查询只要对应位为1,则为重复,因为bitmap是一种非常省空间的数据结构,所以能够满足内存在1G之内的要求



  

老王代码写的太好,却被判了死罪...


面试官问:数据库 delete 表数据,磁盘空间还是被一直占用,为什么?


内推上市公司.NET高级开发工程师 !!


浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

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

手机扫一扫分享

分享
举报