题目
面试真题：经典海量数据处理题最详解析（下）
解题思路
前言 大家好，我是鬼仔，今天接着和大家聊聊 海量数据处理题的解题思路。 前情概要： 在上篇中，问题原形是在海量数据中找出重复次数最多的一个/前N个数据，我们的解决方法是： 分而治之/Hash映射 + HashMap/前缀树统计频率 + 堆/快速/归并排序。具体可见： 面试真题：经典海量数据处理题最详解析（上） 。 今天给大家介绍下海量数据处理题的另一种常见题型：在海量数据中找出第k大/中位数/不重复或重复的数字，解决方法关键还是在于分治，通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内处理数据。一句话：分就完事了！不过今天七夕好像不太方便这么说... 除此之外，鬼仔还会给大家介绍一种大数据场景中常用的算法： 位图法（BitMap）。话不多说，咱们马上进入实战！ 公众号：码农鬼仔，专注分享算法知识｜面试技巧｜职场感悟｜内推信息。 一、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。 整数int有4个byte，所有整数个数有2^32，这里可以继续使用分而治之、hash映射的方法，即对于每个整数x，取hash(x)并模N，N代表划分的小文件个数，这样相同的整数会存入同一个文件，接着通过HashMap统计每个小文件中整数出现的频率（key为整数，value为频率），最后value为1的整数即为所求。 除此之外，我们还可以使用一种特殊的数据结构：位图（BitMap）。 位图的思想是用bit数组来记录0-1两种状态，可以将具体数据映射到这个bit数组的对应位置，bit数组中0表示数据存在，1表示数据不存在。举个例子，利用位图表示0-5中的元素，0-5中只有6个数，所以用6bit足以表示，例如3可以表示为[0,0,0,1,0,0]。位图在大量数据查询、去重等应用场景中使用的比较多，这个算法具有比较高的空间利用率。 回到该题，要找出不重复的整数，那么一个整数可以有三种状态，即不存在、存在1次、存在多次，根据题目需要找出的是存在1次的整数。对于三种状态只用0或1肯定是表示不了的，采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。具体做法为：首先遍历所有整数，查看对应位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。最后遍历位图，找出01对应的整数，即为2.5亿整数中只出现一次的整数。 我们也可以采用两个BitMap，即第一个Bitmap存储的是整数是否出现，接着，在之后的遍历先判断第一个BitMap里面是否出现过，如果出现就设置第二个BitMap对应的位置也为1，最后遍历BitMap，仅仅在一个BitMap中出现过的元素，就是不重复的整数。 二、已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。 这类题目使用位图法最为简单，每个号码八位数，不考虑实际情况，8位最多99 999 999，一共有10^8种情况，也就是需要10^8位bit，大概12.5M内存即可。申请一个数组，遍历所有号码，将号码对应的bit置为1，最后统计bit位1的数量即为不同的号码数。 三、5亿个int整数找它们的中位数 我们先明确中位数的定义：中位数是按顺序排列的一组数据中居于中间位置的数，即在这组数据中，有一半的数据比他大，有一半的数据比他小，如果这组数据有偶数个，那么取中间的两个数值的平均数作为中位数。 解法一：当内存不足以存放5亿个int整数时，我们依然使用分而治之的方法，但hash映射分成小文件的时候需要注意，我们要保证把数据分散到不同文件中时仍然保持着顺序，即按数值大小进行分流，这样才能找到正确的中位数。 我们遍历这5亿个int整数时，考虑其二进制的最高位，按照最高位（符号位，0表示正数，1表示负数）进行二分，即最高位为1存入文件a，最高位为0存入文件b，这样文件a中的数是一定比文件b中的数小。 统计文件a和文件b中的整数个数，如果文件a和文件b中的整数个数相同，那么中位数则是文件a中的最小值和文件b中的最大值的平均值。如果文件a中的整数个数小于文件b，那么中位数肯定在文件b中，反之亦然。 如果文件a或文件b中的整数还是无法直接读取进内存中，那么继续使用上个步骤的方法进行分流，并判断中位数所处的位置，直到中位数所在的那部分数据大小可以直接放到内存中，然后对这部分排序，计算出中位数的值。 解法二：空间换时间，巧妙利用大小堆。这其实可以用力扣295题（数据流的中位数）的方法进行解答，我摘抄下高赞的解法给同学们参考下： 题目： 解答： 代码（Java）： class MedianFinder { PriorityQueue l = new PriorityQueue<>((a,b)->b-a); PriorityQueue r = new PriorityQueue<>((a,b)->a-b); public void addNum(int num) { int s1 = l.size(), s2 = r.size(); if (s1 == s2) { if (r.isEmpty() || num <= r.peek()) { l.add(num); } else { l.add(r.poll()); r.add(num); } } else { if (l.peek() <= num) { r.add(num); } else { r.add(l.poll()); l.add(num); } } } public double findMedian() { int s1 = l.size(), s2 = r.size(); if (s1 == s2) { return (l.peek() + r.peek()) / 2.0; } else { return l.peek(); } } } 时间复杂度：addNum 函数的复杂度为 O(logn)；findMedian 函数的复杂度为 O(1) 空间复杂度：O(n) 总结 面试真题之经典海量数据处理题系列到这里就结束了，还有一些类似的变形题我就不赘述了。 同学们面试的时候要先弄清楚题意，再来思考作答，有疑惑的地方可以大胆地向面试官提问，确保自己没有遗漏细节，然后再根据以前做过的海量数据题寻找相似的思路。 相信同学们跟着鬼仔学完这个系列，以后面试中再也不会怕遇到 海量数据题了！ 最近牛客在搞一个秋招同行计划，邀请大家一起记录自己的笔试，面试经历，写一篇讨论帖@周周~ 就可以得100牛币 反正不限制字数和题材，写的好的还可以拿到50京东卡、周边、一些技术书等，大家冲起来！ 活动详情：https://www.nowcoder.com/link/bgzz2023 希望大家能够给鬼仔点个收藏+关注，你的支持是鬼仔更新的动力！后面鬼仔会持续分享面试经验 & 算法相关的专业知识，点关注、不迷路～ 更多模拟面试 查看更多 > 模拟面试第 6 名 美团 模拟面试 有人3分钟前测试并获得了面试报告 模拟面试第 15 名 哔哩哔哩 模拟面试 有人27分钟前测试并获得了面试报告 (17) (138) 分享 举报 精华采集 浏览5379
讨论区
说点什么吧~
题目列表
现代C++的特性，tcp/ip https，然后问了一下如果你设计vector怎么设计
测试提米1
11111111111111111
我丢
好的好的
刚刚
eeeee33453453sdfsfsdf,dfdfgdfg
卡尔曼滤波和误差卡尔曼滤波的区别。
VINS-Mono 中的滑动窗口算法
为什么 SLAM 需要滑动窗口算法?
VIO系统会存在那些问题？如何解决？
最小二乘问题建模的两个要素
视觉与IMU的融合的优势
单应矩阵的理解
剔除离散点有哪些方法
边缘化的意义
卡尔曼滤波和误差卡尔曼滤波的区别
VINS-Mono 中的滑动窗口算法
为什么 SLAM 需要滑动窗口算法?
VIO系统会存在那些问题？如何解决？
最小二乘问题建模的两个要素
视觉与IMU的融合的优势
单应矩阵的理解
剔除离散点有哪些方法
边缘化的意义
卡尔曼滤波和误差卡尔曼滤波的区别
VINS-Mono 中的滑动窗口算法
为什么 SLAM 需要滑动窗口算法?
VIO系统会存在那些问题？如何解决？
最小二乘问题建模的两个要素
视觉与IMU的融合的优势
单应矩阵的理解
剔除离散点有哪些方法
边缘化的意义
这个事题目标题这个事题目标题这个事题目标题
现代C++的特性，tcp/ip https，然后问了一下如果你设计vector怎么设计
需解锁获得
100～200之间不是3的倍数的数之和是多少？
建筑工地有一批砖，最上层两块砖，第2层6块砖，第3层10块砖……(如图)，依次每层比其上一层多4块，已知最下层有2106块砖，这堆砖共有多少块?
从午夜零时到中午12时，时针和分针共重叠( )次。
从午夜零时到中午12时，时针和分针共重叠( )次。
1111
12312
12
1
dd
父子三个,娘儿三个,老两口儿,哥儿俩,一共几个人？
老大撺掇老C++二让老三告诉老四说老五的老二老大了哈哈哈哈哈哈
爷俩，娘俩，老两口儿，兄弟一个，一共几口人？
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
学校有808个同学，分乘6辆汽车去春游，第一辆车已经接走了128人，如果其余5辆车乘的人数相同，最后一辆车乘了几个同学呢?
有10把不同的锁，开这10把锁的10把钥匙混在一起了，最多要试多少次，才能把这10把锁和钥匙全部配对。
3只猫3天吃了3只老鼠，照这样的效率，9只猫9天能吃( ) 只。
锯一根10米长的木棒，每锯一段要2分钟。如果把这根木棒锯成相等的5段，一共要( )分钟。
一只蜗牛在10米深的井底向上爬，每小时爬上3米后要滑下2米，这只蜗牛要( )小时才能爬出井口。
用一根绳子绕树三圈余30厘米，如果绕树四圈则差40厘米，树的周长有( )厘米，绳子长( )厘米。
有一串彩珠，按“2红3绿4黄”的顺序依次排列。第600颗是( )颜色。
同学们进行广播操比赛，这个全班正好排成相等的6行。小红排在第二行，从头数，她站在第5个位置，从后数她站在第3个位置，这个班共有( )人。
7年前，妈妈年龄是儿子的6倍，儿子今年12岁，妈妈今年( )岁。
文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字文字
40个梨分给3个班，分给一班20个，其余平均分给二班和三班，二班分到( )个。
深蓝学院1111111，题目不要上传图片
当代网友是怎么表达遗憾的 一个人迷茫哭的emo文案
1111
222222222
测试这标签
句句不提坎坷却全是遗憾的文案
当代网友能够把悲伤写到什么程度？
555555555555555555
1233211234567
1111
1
请输入题干标题13
fadfadf请输入题干标题请输入题干标题1
请输入题干标题4444 1前台上传的题目
记一次字节跳动前端面试，四轮技术面通过，已拿offer
毕业一年多，职场小油条（运营）经历
4399;英雄互娱-文案创意运营类面经 其他游戏公司适用
毕业半年遇到互联网裁员潮，文科生、艺术生转型自救之路
字节电商战略数据分析 社招五面面经 求OC
【最全】2021宝洁offer经验分享（网申+面试）
非科班半年转Java开发经验贴
面经：华为海思暑期实习 数字IC设计岗
数分求职分享 | 忠于内心终有所得
放弃了离家近的工作，我又一次开启沪飘之旅。
java offer已有，下一步---妹子
双非2年工作经验，裸辞斩获字节运营offer
给师弟师妹的建议：去看看这个世界
（牛客回馈贴）学姐纯干货|普通本科最强逆流而上指南1
字节飞书前端三面(55min)
双非本科非科班 抖音Android面筋（被调剂到iOS了）
暑期实习春招面经回馈（阿里美团百度字节快手谷歌亚马逊）
字节抖音电商一面凉经
【审计岗】如何制作简历？
第一份金融实习怎么找？最全找实习干货贴分享来了
同学，不要再那么单纯了，他们不值得
关于银行的offer选择
一年的准备！阿里终于圆梦了
工作4年，走了太多的弯路，分享下我的经历希望能给大家避下坑
建行省分只有一面
难以忘怀的大四异地实习经历
字节跳动五轮技术面终于收获意向书（后端开发）
华为优招 消费者BG终端芯片-嵌入式面经
个人秋招经验总结（前端方向）
大数据开发，不知道叫什么帖
大华海康硬件工程师三面（已offer）
金融行业薪酬大盘点，银行真的太香了！
【字节跳动-飞书-运营实习生】 一面面经
毕业季大家有什么舍不得的那个他（她）嘛？
嘉士伯管培AI面经整理分享
秋招复盘——普通硕士做嵌入式也可以拿到50w年薪
（面试复盘）字节跳动互娱研发提前批前端面经
2021秋招留学生华为单板硬件面经
面试复盘|字节跳动面经-技术中台-一二三凉面
互联网直播运营丨三段面试经历告诉你应该这样面
字节 滴滴 好未来 社招产品面经
财会入门必看：有关ACCA的一些初浅攻略
如何准备交互/ux设计校招-没有作品怎么办
秋招总结 | 还是成为了一名光荣的新时代农民工
运维岗位面经，拿到网易，京东offer
20机械制造类求职经历：东风日产、华为结构与材料工程师等
2022秋招【中国建筑3311】【投资岗】面经
滴滴秋储后端实习生面经+秋招正式批面经（均已offer）
硬件开发岗面经（TCL华星光电、联发科技、中兴等）
双非菜鸟前端秋招总结帖
21届秋招记录——银行篇
不幸中的万幸——转正后被裁员！
面试真题：经典智力题最详汇总（中）
面试真题：经典智力题最详汇总（下）
【阿里设计岗面试经验总结】如何1个月内通过4轮面试
我和牛客的故事之22届银行秋招记录（雄安新区+天津）
面试复盘 | 2022届 大疆秋招 测试开发 完整面经
AWS亚马逊 23暑期实习 PM 面经+流程
面试真题：经典智力题最详汇总（上）
华为，中兴，百度，CVTE，海康威视热乎乎的面经
一年半经验前端社招——拼多多（已面完hr）
秋招总结|咸鱼的懒汉秋招
如果回到一年前，我会做出哪些不一样的决定
CNKI(同方知网)+社招+java
去年秋招的一些经验和建议，回馈贴
看了我弟写的简历，作为深信服HR的我破防了！
秋招总结｜双非本/非科班/零offer，没有逆袭，但不放弃！
美团面试官哥哥太温柔了，我哭死
阿斯利康市场营销管培生群面-终面面经（已offer）
秋招cpp面试总结（百度，字节，阿里等）
字节提前批《高频汇总之前端水真的不深》
硬件岗秋招小结
春招 Golang实习面经
秋招银行+国企类笔试面试经验。
互联网就业形势这么差，我真的建议你试试金融！
23届联想面经分享： 秋招上岸
秋招总结 | 三本前端秋招之路
菜鸡21届秋招总结-前期准备、面试、谈薪资待遇
秋招总结&Java心得（双非硕士，已拿11+5家Offer）
20年工业机器人面试求职经历：华为、哈工大机器人、汇川技术等
分享一下大疆2022年春招体验设计面试的经验！
数字IC后端设计求职面经
网易互娱游戏文案策划（暑期实习）笔试一面二面三面经验总结
计算机网络常见面试题
二本院校生的考公逆袭路
资源分享|各学校计算机类历年考研真题汇总
大疆硬件工程师三轮面经&还愿offer
sre/运维开发社招面经
11.11蓝月亮产品策划终面｜全过程持续更新中
HR岗校园招聘面经合集（已上岸）
校招面霸成长手册
金融/互联网/国企秋招经验分享
得力国内营销面经
游戏本地化/运营/发行面经（tap运营offer已拒）
工资与五险一金计算
分享下菜鸡的Java秋招总结
延锋内饰春招面经
戴尔大客户销售面经
秋招｜SHEIN两轮面试经历分享
宝洁市场研究部CMK，分享一下自己入职一年的经历和感受
面试真题：经典海量数据处理题最详解析（下）
字节提前批《高频汇总之测试篇距离上岸的一步之遥》
广联达面经技术岗专场：测试、前端、后端
一次不成文的数据分析秋招经历
C++STL用过vectorstring，函数重载回答不准确，函数重载两种方式回答出成员函数一种。
可口可乐 AI面+游戏
终于大橘已定，分享一波测开面经（美团、小米、华为、阿里等）
被疫情逼得gap year的完全菜鸡的春招之路。
从发展角度，谈谈offer选择
数据分析 面经（已拿到offer）
银行科技岗/研发中心/数据中心秋招经验总结帖
【银行干货】23届想进银行，该如何高效备考
西山居游戏策划（非文案方向）笔试/面经 个人春招之路总结
ZURU 项目管培 面经
双非渣硕的字节NLP算法三面+HR面面经(已OC)
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
【虾皮/Shopee】2022届同学试用期感想
来自双非大三拿到字节跳动实习offer求职准备建议（非广告）
腾讯三面已上岸
22届校招-浙商银行总行-总行机关单位-求职攻略
恒生校招内推 测试秋招八股文集锦——经典网络篇 用友面经（一二面，已oc） 替你们整理好了！计算机专业最适合去的四类国企！附薪资待遇对比 秋招招聘汇总+避雷公司8.16更新+简历指导(已指导百人) 不想去互联网大厂卷？这些小而美公司不香吗？ 谈薪技巧和注意事项，怎么为自己多争取1~2k 我的秋招结束了 【2023秋招&提前批】互联网招聘信息最新汇总9月10日更新 【亚信安全】23届校园招聘正式启动啦 【求职面试】初级产品经理面试应该注意什么？ 干货帖| 招商银行信用卡中心校招怎么样 腾讯音乐TME 20220908笔试题解 b站测开实习一面 中兴最全面经汇总：硬件、软开、算法、测试 双非本科，面试三十多家企业总结出的宝藏面试经验 9月13日，微众银行笔试 9月13日微众银行笔试代码 20220913百度2023秋招研发B卷题解 面试常问-Spring Cloud篇23届秋招一点小小的牢骚
当面试官提问：你有什么要问我的吗？该如何回答 上海曼伦2023内推 | 可查询所有岗位进度 【持续更新】这些外企公司已经开始秋招了！快冲呀 美团面经（一二面，已挂） 【23秋招银行招聘信息汇总】最新汇总9月14日这个事题目标题这个事题目标题这个事题目标题
扫描二维码
请添加深了个蓝微信
请备注【智商测验题库】
编辑题目
题干
解题思路
设置题目所属题包
- 二级分类专属题包
- 测试题包1
- 网抑云
- 牛客网爬的数据2
- nkw爬取数据
请选择题目所属岗位（请最多选择6个）
请选择题目所属公司
- 测试公司
- 计算机
- test专用
- 大疆无人机
- 哔哩哔哩
- 百度智能
- 字节跳动
- 英伽教育
- 北京校苑
- 环球赛乐
- 深蓝前沿科技
解题思路解锁方式
您还有0次解锁机会，是否解锁本题思路？
官方微信公众号
扫码下载APP