网易首页 > 网易号 > 正文 申请入驻

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

0
分享至

作者:Java干货分享来源:今日头条

今天,我们来聊一道常见的考题,也出现在腾讯面试的三面环节,非常有意思。具体的题目如下:

  • 文件中有40亿个QQ号码,请设计算法对QQ号码去重,相同的QQ号码仅保留一个,内存限制1G。

这个题目的意思应该很清楚了,比较直白。为了便于大家理解,我来画个动图玩玩,希望大家喜欢。


能否做对这道题目,很大程度上就决定了能否拿下腾讯的offer,有一定的技巧性,一起来看下吧。

在原题中,实际有40亿个QQ号码,为了方便起见,在图解和叙述时,仅以4个QQ为例来说明。

方法一:排序

很自然地,最简单的方式是对所有的QQ号码进行排序,重复的QQ号码必然相邻,保留第一个,去掉后面重复的就行。

原始的QQ号为:


排序后的QQ号为:


去重就简单了:


可是,面试官要问你,去重一定要排序吗?显然,排序的时间复杂度太高了,无法通过腾讯面试。

方法二:hashmap

既然直接排序的时间复杂度太高,那就用hashmap吧,具体思路是把QQ号码记录到hashmap中:

mapFlag[123] = true
mapFlag[567] = true
mapFlag[123] = true
mapFlag[890] = true

由于hashmap的去重性质,可知实际自动变成了:

mapFlag[123] = true
mapFlag[567] = true
mapFlag[890] = true

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

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

方法三:文件切割

显然,这是海量数据问题。看过很多面经的求职者,自然想到文件切割的方式,避免内存过大。

可是,绞尽脑汁思考,要么使用文件间的归并排序,要么使用桶排序,反正最终是能排序的。

既然排序好了,那就能实现去重了,貌似就万事大吉了。我只能坦白地说,高兴得有点早哦。

接着,面试官又要问你:这么多的文件操作,效率自然不高啊。显然,无法通过腾讯面试。

方法四:bitmap

来看绝招!我们可以对hashmap进行优化,采用bitmap这种数据结构,可以顺利地同时解决时间问题和空间问题。

在很多实际项目中,bitmap经常用到。我看了不少组件的源码,发现很多地方都有bitmap实现,bitmap图解如下:


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

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


由此可见,一个unsigned char类型的数据,可以标识0~7这8个整数的存在与否。以此类推:

  • 一个unsigned int类型数据可以标识0~31这32个整数的存在与否。
  • 两个unsigned int类型数据可以标识0~63这64个整数的存在与否。

显然,可以推导出来:512MB大小足够标识所有QQ号码的存在与否,请注意:QQ号码的理论最大值为2^32 - 1,大概是43亿左右。

接下来的问题就很简单了:用512MB的unsigned int数组来记录文件中QQ号码的存在与否,形成一个bitmap,比如:

bitmapFlag[123] = 1
bitmapFlag[567] = 1
bitmapFlag[123] = 1
bitmapFlag[890] = 1

实际上就是:

bitmapFlag[123] = 1
bitmapFlag[567] = 1
bitmapFlag[890] = 1

然后从小到大遍历所有正整数(4字节),当bitmapFlag值为1时,就表明该数是存在的。

而且,从上面的过程可以看到,自动实现了去重。显然,这种方式可以通过腾讯的面试。

扩展练习一

文件中有40亿个互不相同的QQ号码,请设计算法对QQ号码进行排序,内存限制1G。

很显然,直接用bitmap, 标记这40亿个QQ号码的存在性,然后从小到大遍历正整数,当bitmapFlag的值为1时,就输出该值,输出后的正整数序列就是排序后的结果。

请注意,这里必须限制40亿个QQ号码互不相同。通过bitmap记录,客观上就自动完成了排序功能。

扩展练习二

文件中有40亿个互不相同的QQ号码,求这些QQ号码的中位数,内存限制1G。

我知道,一些刷题经验丰富的人,最开始想到的肯定是用堆或者文件切割,这明显是犯了本本主义错误。直接用bitmap排序,当场搞定中位数。

扩展练习三

文件中有40亿个互不相同的QQ号码,求这些QQ号码的top-K,内存限制1G。

我知道,很多人背诵过top-K问题,信心满满,想到用小顶堆或者文件切割,这明显又是犯了本本主义错误。直接用bitmap排序,当场搞定top-K问题。

扩展练习四

文件中有80亿个QQ号码,试判断其中是否存在相同的QQ号码,内存限制1G。

我知道,一些吸取了经验教训的人肯定说,直接bitmap啊。然而,又一次错了。根据容斥原理可知:

因为QQ号码的个数是43亿左右(理论值2^32 - 1),所以80亿个QQ号码必然存在相同的QQ号码。

海量数据的问题,要具体问题具体分析,不要眉毛胡子一把抓。有些人完全不刷题,肯定不行。有些人刷题后不加思考,不会变通,也是不行的。好了,先说这么多。我们也会一步一个脚印,争取每篇文章讲清讲透一件事,也希望大家阅读后有所收获,心情愉快

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
纪实:女子开车追尾宝马,下车后搂着大哥撒娇:私下里什么都好说

纪实:女子开车追尾宝马,下车后搂着大哥撒娇:私下里什么都好说

诸子史家
2022-06-27 23:34:16
科比坠机黑匣子破译完毕,最后录音公布:满是不舍与父爱

科比坠机黑匣子破译完毕,最后录音公布:满是不舍与父爱

小叶子说球
2022-06-27 13:28:15
俄军改变了轰炸策略!乌克兰:破坏性巨大!

俄军改变了轰炸策略!乌克兰:破坏性巨大!

清史明月照人还
2022-06-28 08:55:17
山东一部长被查!

山东一部长被查!

大小新闻
2022-06-28 09:51:14
演员李崇霄去世,享年51岁,曾与宋丹丹合作多部经典电视剧

演员李崇霄去世,享年51岁,曾与宋丹丹合作多部经典电视剧

猫眼电影
2022-06-27 12:22:57
古人说,为什么不要吃鳝鱼

古人说,为什么不要吃鳝鱼

人文收藏艺术大师
2022-06-27 09:11:52
唐山新变局!全国严打,赔偿被截胡,主犯难逃一死,从犯背景复杂

唐山新变局!全国严打,赔偿被截胡,主犯难逃一死,从犯背景复杂

眠于流年
2022-06-26 18:48:46
国务院:免去张务锋的国家粮食和物资储备局局长职务

国务院:免去张务锋的国家粮食和物资储备局局长职务

界面新闻
2022-06-27 16:35:23
微信真史诗级更新,再也不怕删错聊天记录

微信真史诗级更新,再也不怕删错聊天记录

中关村在线
2022-06-28 00:48:06
汶川地震幸存的“神车”:只因车牌特殊,公安部特批,入驻纪念馆

汶川地震幸存的“神车”:只因车牌特殊,公安部特批,入驻纪念馆

孤风婉史
2022-06-27 14:12:01
女排名单出炉:丁霞金烨杨涵玉落选!王艺竹出场,缪伊雯或打主攻

女排名单出炉:丁霞金烨杨涵玉落选!王艺竹出场,缪伊雯或打主攻

金毛爱女排
2022-06-28 12:40:31
解放军为何不在香港、澳门两个特别行政区招兵?一共有四大原因

解放军为何不在香港、澳门两个特别行政区招兵?一共有四大原因

小圣杂谈原创
2022-06-27 21:48:18
1年4900万!内马尔赚翻,踢1年=C罗奋斗2年,姆巴佩愿望落空

1年4900万!内马尔赚翻,踢1年=C罗奋斗2年,姆巴佩愿望落空

我的护球最独特
2022-06-28 09:48:38
4100万顶薪,直接买断!火箭为何愿意白给沃尔钱?2点原因是关键

4100万顶薪,直接买断!火箭为何愿意白给沃尔钱?2点原因是关键

野球帝
2022-06-28 12:05:43
性是夫妻间的大事

性是夫妻间的大事

一频线
2022-06-28 00:44:34
来自70岁大爷的时尚,我表示看不懂...

来自70岁大爷的时尚,我表示看不懂...

洋洋娱乐烩
2022-06-27 18:54:19
财联社6月28日电,法国总统马克龙告诉拜登,阿联酋王储告诉他,沙特阿拉伯每天可以增产15万桶,甚至更多。

财联社6月28日电,法国总统马克龙告诉拜登,阿联酋王储告诉他,沙特阿拉伯每天可以增产15万桶,甚至更多。

财联社
2022-06-28 00:36:13
在北京,你已经买不起自行车了

在北京,你已经买不起自行车了

INSIGHT视界
2022-06-27 22:49:03
她带领农村女孩走出农村,一生奉献给大山,却让学生永远不要回来

她带领农村女孩走出农村,一生奉献给大山,却让学生永远不要回来

洞察视鉴
2022-06-28 01:40:02
宝马“小号X5”即将上市,车长4米5,5.7秒破百,仅28万起售

宝马“小号X5”即将上市,车长4米5,5.7秒破百,仅28万起售

车资讯全视角
2022-06-28 12:56:16
2022-06-28 15:10:44
Nodejs开发
Nodejs开发
分享只有程序员懂的干货
639文章数 6396关注度
往期回顾 全部

科技要闻

为什么字节跳动还在轰炸式招聘?

头条要闻

北约新战略构想修改措辞:将俄等同于冷战时期的苏联

头条要闻

北约新战略构想修改措辞:将俄等同于冷战时期的苏联

体育要闻

全红婵:希望下次可以更努力争取金牌

娱乐要闻

60岁刘德华片场被偷拍 疑回头怒瞪狗仔

财经要闻

汽车要闻

现代全新电动车细节图 溜背设计+流媒体后视镜

态度原创

家居
健康
亲子
手机
数码

家居要闻

4房改成2房!有娃家庭全屋竟黑白色调?

更年期有这些症状要看医生!

亲子要闻

浙江一保姆疏忽致2岁女童坠亡,爸爸一夜白头:不施救还撒谎

手机要闻

iPhone 14 Pro最大升级,相机参数亮眼,国产手机能打的有几个?

数码要闻

iPad mini 7曝光,A16+120Hz高刷,预定游戏神器

进入关怀模式