首页 > 面试真题:经典海量数据处理题最详解析(下)

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

头像
码农鬼仔
编辑于 08-04 13:49 APP内打开
赞 13 | 收藏 107 | 回复9 | 浏览2119

前言

大家好,我是鬼仔,今天接着和大家聊聊 海量数据处理题的解题思路。

前情概要: 在上篇中,问题原形是在海量数据中找出重复次数最多的一个/前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<Integer> l = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> 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

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

更多模拟面试

7条回帖

回帖
加载中...
话题 回帖