面试真题:经典海量数据处理题最详解析(上)

本文正在参与【[ 面霸养成记 ] 】 征文活动,一起来聊聊校招的那些事吧,牛客周边和百元京东卡等你来领~


前言

大家好,我是鬼仔。之前鬼仔整理了有关智力题的系列面试题,感兴趣的同学们可以复习下:

除了智力题,技术岗同学面试的时候常常会遇到另一种特殊题型:海量数据处理题

为了帮助同学们在面试中拿下海量数据处理题,鬼仔特意准备了该系列,不仅分析解读经典面试真题,让同学们直面感受该类题型的难度,以及对应的解决方案,而且还会对该类题型进行总结升华,题目是无限的,但方法是有限的,以不变应万变,有形化无形,才能真正拿下海量数据处理题!大家记得关注鬼仔哦,这样才能第一时间收到更新信息~

海量数据处理面试题其实有着很强的规律性,因为它们面临的场景都大同小异,那就是数据量太大了,而机器内存不足,无法直接将海量数据直接读进内存中进行处理。

此时我们常用的方法就是Hash映射、分而治之,将大数据切分为多块小数据,逐个击破,这其实也是Map Reduce的思想。除了空间复杂度的优化,我们还可以通过巧妙的数据结构和算法来优化时间复杂度,比如HashMap、BitMap、前缀树等数据结构和堆排序、topk等算法。

今天鬼仔先给大家分析一些经典的面试真题,这些都是面试中最常见的海量数据处理题,同学们只要掌握了这些题,可以毫不夸张地说,可以秒杀掉90%该类题型。如果不能那你过来把鬼仔的头打歪!

公众号:码农鬼仔,专注分享算法知识|面试技巧|职场感悟|内推信息。

一、海量日志数据,提取出某日访问百度次数最多的IP。

假设内存无穷大,我们可以用常规的HashMap(ip,value)来统计ip出现的频率,统计完后利用排序算法得到次数最多的IP,这里的排序算法一般是堆排序或快速排序。

但考虑实际情况,我们的内存是有限的,所以无法将海量日志数据一次性塞进内存里,那应该如何处理呢?很简单,分而治之!即将这些IP数据通过Hash映射算法划分为多个小文件,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文件中出现频率最大的IP,最后在这1000个最大的IP中,找出那个频率最大的IP,即为所求(是不是很像Map Reduce的思想?)。

这里鬼仔再多说一句:Hash取模是一种等价映射算法,不会存在同一个元素分散到不同小文件中的情况,这保证了我们分别在小文件统计IP出现频率的正确性。我们对IP进行模1000的时候,相同的IP在Hash取模后,只可能落在同一个小文件中,不可能被分散的。因为如果两个IP相等,那么经过Hash(IP)之后的哈希值是相同的,将此哈希值取模(如模1000),必定仍然相等。

总结一下,该类题型的解决方法分三步走:

  1. 分而治之、hash映射;
  2. HashMap(或前缀树)统计频率;
  3. 应用排序算法(堆排序或快速排序)。

如果将题目改为:海量日志数据,提取出某日访问百度次数最多的前N个IP。牛油们知道怎么处理吗?把答案写在评论区吧~

二、搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询长度不超过 255 字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

我们首先分析题意:一千万个记录,除去重复后,实际上只有300万个不同的记录,每个记录假定为最大长度255Byte,则最多占用内存为:3M*1K/4=0.75G<1G,完全可以将所以查询记录存放在内存中进行处理。相较于第一道题目,这题还更简单了,直接HashMap(或前缀树)+堆排序即可。

具体做法如下:

  1. 遍历一遍左右的Query串,利用HashMap(或前缀树)统计频率,时间复杂度为O(N),N=1000万;
  2. 建立并维护一个大小为10的最小堆,然后遍历300万Query的频率,分别和根元素(最小值)进行对比,最后找到Top K,时间复杂度为N‘logK,N‘=300万,K=10。

三、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

经过前两道题的训练,第三道题相信大家已经游刃有余了,这类题型都有相同的特点:文件size很大,内存有限,解决方法还是经典三步走:分而治之 + hash统计 + 堆/快速排序。

具体做法如下:

  1. 分而治之、hash映射:遍历一遍文件,对于每个词x,取hash(x)并模5000,这样可以将文件里的所有词分别存到5000个小文件中,如果哈希函数设计得合理的话,每个文件大概是200k左右。就算其中有些文件超过了1M大小,还可以按照同样的方法继续往下分,直到分解得到的小文件的大小都不超过1M;
  2. HashMap(或前缀树)统计频率:对于每个小文件,利用HashMap(或前缀树)统计词频;
  3. 堆排序:构建最小堆,堆的大小为100,找到频率最高的100个词。

四、给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

每个url是64字节,50亿*64=5G×64=320G,内存限制为4G,所以不能直接放入内存中。怎么办?分而治之!

具体做法如下:

  1. 遍历文件a中的url,对url进行hash(url)%1000,将50亿的url分到1000个文件中存储(a0,a1,a2.......),每个文件大约300多M,对文件b进行同样的操作,因为hash函数相同,所以相同的url必然会落到对应的文件中,比如文件a中的url1与文件b中的url2相同,那么它们经过hash(url)%1000也是相同的。即url1落入第n个文件中,url2也会落入到第n个文件中。
  2. 遍历a0中的url,存入HashSet中,同时遍历b0中的url,查看是否在HashSet中存在,如果存在则保存到单独的文件中。然后以此遍历剩余的小文件即可。

小结

讲完了这四道例题,我们再来总结一下,这几道题都有一个共性,那就是要求在海量数据中找出重复次数最多的一个/前N个数据,我们的解决方法也很朴实:分而治之/Hash映射 + HashMap/前缀树统计频率 + 堆/快速/归并排序,具体来说就是先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数,最后利用堆这个数据结构高效地取出前N个出现次数最多的数据。

除了上述的这些题型,海量数据处理题还有其他类型,鬼仔过两天会继续更新该系列,相信同学们跟着鬼仔学完这个系列,以后面试中再也不会怕遇到海量数据处理题了!

最近牛客在搞一个秋招同行计划,邀请大家一起记录自己的笔试,面试经历,写一篇讨论帖@周周~ 就可以得100牛币
反正不限制字数和题材,写的好的还可以拿到50京东卡、周边、一些技术书等,大家冲起来!
活动详情:https://www.nowcoder.com/link/bgzz2023

希望大家能够给鬼仔点个收藏+关注,你的支持是鬼仔更新的动力!后面鬼仔会持续分享面试经验 & 算法相关的专业知识,点关注、不迷路~

#面试八股文##海量数据##鬼仔带你学算法##面经##提前批#
全部评论
面试真题:经典海量数据处理题最详解析(下) https://www.nowcoder.com/discuss/1004269
2 回复 分享
发布于 2022-08-04 13:51
都看到这里了,不关注一下#鬼仔带你学算法#
2 回复 分享
发布于 2022-08-02 11:08
1 回复 分享
发布于 2022-08-02 11:16
太顶了
点赞 回复 分享
发布于 2022-08-22 17:07 广东
华为云内推, go、java、c/c++研发、测试,大量hc!!! 欢迎联系!!
点赞 回复 分享
发布于 2022-08-04 14:47
网易内推看过来😁
点赞 回复 分享
发布于 2022-08-04 12:23
华为无线23届校招内推找我
点赞 回复 分享
发布于 2022-08-04 10:43
我有点疑惑,在第三题中,需要取出前100的词频,那么需要取出每个文件的前100放在一起再进行比较出前100才对(极端情况下可能top100全在同一个文件),这样5000*100*16byte/1000/1000 = 8M ,内存放不下啊😮
点赞 回复 分享
发布于 2022-08-04 00:23
感觉是数据库join那一套
点赞 回复 分享
发布于 2022-08-03 08:34
很有用,期待经典海量数据处理题最详解析(下)
点赞 回复 分享
发布于 2022-08-03 07:42
点赞 回复 分享
发布于 2022-08-02 18:34
tql
点赞 回复 分享
发布于 2022-08-02 18:33
可以来深信服看看哦~校招内推NTANGyK(投递链接,大厂待遇,本科21-48w+,硕士24-54w+!!无责底薪20W+,绩效加各种补贴!多次调薪机会!超丰富下午茶有爱氛围!!我们看实习,更看能力!能力优秀者没有实习经历没有985也能录取!)
点赞 回复 分享
发布于 2022-08-02 18:18
点赞 回复 分享
发布于 2022-08-02 12:17
催更催更
点赞 回复 分享
发布于 2022-08-02 11:57
学到了
点赞 回复 分享
发布于 2022-08-02 11:39
厉害厉害厉害,太干了!
点赞 回复 分享
发布于 2022-08-02 11:12

相关推荐

点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
51
446
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务