精华内容
下载资源
问答
  • 介绍了一个海量数据处理面试题,也对海量数据处理方法进行了总结。
  • 海量数据处理面试题

    2018-12-26 14:34:57
    海量数据处理 !!!!!
  • 所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为)中。这样每个小文件的大约为300M。遍历文件b,采取和a相同的方式...
  • 十道海量数据处理面试题与十个方法大总结,主要面向互联网海量数据应用,海量数据筛选,排序等
  • 海量数据处理面试题方法总结

    千次阅读 2016-06-09 18:45:52
    第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。  首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。...

    第一部分、十道海量数据处理面试题

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

          首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

    或者如下阐述(雪域之鹰):
    算法思想:分而治之+Hash
    1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理; 
    2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址; 
    3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
    4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;


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

        典型的Top K算法,还是在这篇文章里头有所阐述,详情请参见:十一、从头到尾彻底解析Hash表算法。
        
        文中,给出的最终算法是:
        第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成统计(之前写成了排序,特此订正。July、2011.04.27);
        第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。
            即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N'*O(logK),(N为1000万,N’为300万)。ok,更多,详情,请参考原文。

        或者:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。


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

        方案:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。

        如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
        对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。


    4、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

        还是典型的TOP K算法,解决方案如下:
        方案1:
        顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
        
        找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。

        对这10个文件进行归并排序(内排序与外排序相结合)。

        方案2:
         一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

        方案3:
        与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。


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

        方案1:可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

        遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,...,a999)中。这样每个小文件的大约为300M。

        遍历文件b,采取和a相同的方式将url分别存储到1000小文件(记为b0,b1,...,b999)。这样处理后,所有可能相同的url都在对应的小文件(a0vsb0,a1vsb1,...,a999vsb999)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

        求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

        方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

        Bloom filter日后会在本BLOG内详细阐述。


    6、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

        方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

        方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。


    7、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

        与上第6题类似,我的第一反应时快速排序+二分查找。以下是其它更好的方法:
        方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

        dizengrong:
        方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:
    又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
    这里我们把40亿个数中的每一个用32位的二进制来表示
    假设这40亿个数开始放在一个文件中。

        然后将这40亿个数分成两类:
          1.最高位为0
          2.最高位为1
        并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
    与要查找的数的最高位比较并接着进入相应的文件再查找

        再然后把这个文件为又分成两类:
          1.次最高位为0
          2.次最高位为1

        并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
        与要查找的数的次最高位比较并接着进入相应的文件再查找。
        .......
        以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。

       附:这里,再简单介绍下,位图方法:
        使用位图法判断整形数组是否存在重复 
        判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。

        位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

        欢迎,有更好的思路,或方法,共同交流。


    8、怎么在海量数据中找出重复次数最多的一个?
       
        方案1:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。


    9、上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。

        方案1:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第2题提到的堆机制完成。


    10、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        方案1:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。


    附、100w个数中找出最大的100个数。

        方案1:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

        方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。

        方案3:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。

    致谢:http://www.cnblogs.com/youwang/

     

    第二部分、十个海量数据处理方法大总结

        ok,看了上面这么多的面试题,是否有点头晕。是的,需要一个总结。接下来,本文将简单总结下一些处理海量数据问题的常见方法,日后,本BLOG内会具体阐述这些方法。

        下面的方法全部来自http://hi.baidu.com/yanxionglu/blog/博客,对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎讨论。

    一、Bloom filter

      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集

      基本原理及要点:
      对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。

      还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

      举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

      注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

      扩展:
      Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

      问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

      根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。


    二、Hashing

      适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存

      基本原理及要点:
      hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
      碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

          扩展:
      d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。

      问题实例:
      1).海量日志数据,提取出某日访问百度次数最多的那个IP。
      IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。


    三、bit-map

      适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

      基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码

      扩展:bloom filter可以看做是对bit-map的扩展

      问题实例:
      1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
      8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。
      2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

      将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。


    四、堆

      适用范围:海量数据前n大,并且n比较小,堆可以放入内存

      基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。

      扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。

      问题实例:
      1)100w个数中找最大的前100个数。
      用一个100个元素大小的最小堆即可。

     

    五、双层桶划分----其实本质上就是【分而治之】的思想,重在“分”的技巧上!

      适用范围:第k大,中位数,不重复或重复的数字
      基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。

      扩展:
      问题实例:
      1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
      有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

      2).5亿个int找它们的中位数。
      这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

      实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。


    六、数据库索引

      适用范围:大数据量的增删改查

      基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。


    七、倒排索引(Inverted index)

      适用范围:搜索引擎,关键字查询

      基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

     以英文为例,下面是要被索引的文本:
        T0 = "it is what it is"
        T1 = "what is it"
        T2 = "it is a banana"

    我们就能得到下面的反向文件索引:

        "a":      {2}
        "banana": {2}
        "is":     {0, 1, 2}
        "it":     {0, 1, 2}
        "what":   {0, 1}

     检索的条件"what","is"和"it"将对应集合的交集。

      正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。

      扩展:
      问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。


    八、外排序

      适用范围:大数据的排序,去重

      基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树

      扩展:

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

      这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。


    九、trie树

      适用范围:数据量大,重复多,但是数据种类小可以放入内存

      基本原理及要点:实现方式,节点孩子的表示方式

      扩展:压缩实现。

      问题实例:
      1).有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
      2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
      3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。


    十、分布式处理 mapreduce

      适用范围:数据量大,但是数据种类小可以放入内存

      基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

      扩展:
      问题实例:
      1).The canonical example application of MapReduce is a process to count the appearances of
    each different word in a set of documents:
      2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
      3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?


    经典问题分析
      上千万or亿数据(有重复),统计其中出现次数最多的前N个数据,分两种情况:可一次读入内存,不可一次读入。

      可用思路:trie树+堆,数据库索引,划分子集分别统计,hash,分布式计算,近似统计,外排序

      所谓的是否能一次读入内存,实际上应该指去除重复后的数据量。如果去重后数据可以放入内存,我们可以为数据建立字典,比如通过 map,hashmap,trie,然后直接进行统计即可。当然在更新每条数据的出现次数的时候,我们可以利用一个堆来维护出现次数最多的前N个数据,当然这样导致维护次数增加,不如完全统计后在求前N大效率高。

      如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形,可以做的改变就是将字典存放到硬盘上,而不是内存,这可以参考数据库的存储方法。

      当然还有更好的方法,就是可以采用分布式计算,基本上就是map-reduce过程,首先可以根据数据值或者把数据hash(md5)后的值,将数据按照范围划分到不同的机子,最好可以让数据划分后可以一次读入内存,这样不同的机子负责处理各种的数值范围,实际上就是map。得到结果后,各个机子只需拿出各自的出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是reduce过程。

      实际上可能想直接将数据均分到不同的机子上进行处理,这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上,而另一个则可能完全聚集到一个机子上,同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个,我们将1000万的数据分布到10台机器上,找到每台出现次数最多的前 100个,归并之后这样不能保证找到真正的第100个,因为比如出现次数最多的第100个可能有1万个,但是它被分到了10台机子,这样在每台上只有1千个,假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的,比如有1001个,这样本来具有1万个的这个就会被淘汰,即使我们让每台机子选出出现次数最多的1000个再归并,仍然会出错,因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上,而是要根据hash 后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。

      而外排序的方法会消耗大量的IO,效率不会很高。而上面的分布式方法,也可以用于单机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。

      另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际中出现最多的那些词作为一个字典,使得这个规模可以放入内存。 

    ok,更多请参见本文总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。以上有任何问题,欢迎指正。谢谢大家。

    展开全文
  • 这对计算机教育界和出版界既是机遇,也是挑战;而专业的建设在教育战略上显得举足轻重
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题,常见的面试题目的方法进行了总结,能够很快得出对应题目的答案
  • 教你如何迅速秒杀掉 海量数据处理面试题.pdf
  • IT常见面试题-海量数据处理面试题集锦,根据实际的面试经验,总结了网上的面试题目,并给出了详细解析
  • 十道海量数据处理面试题(卷).doc
  • 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也...十道海量数据处理面试题与十个方法大总结的一般抽象性总结。
  • 问题1 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想...之前在此文,海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用Trie树统计每个词出现的次数,时间复杂...

    本文参考链接:https://blog.csdn.net/u013949069/article/details/78056102?utm_source=copy

    1. 问题1
      一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

    之前在此文,海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用Trie树统计每个词出现的次数,时间复杂度是O(nle)(le表示单词的平均长度),然后是找出出现最频繁的前10个词。也可以用堆来实现(具体的操作可参考第三章、寻找最小的k个数),时间复杂度是O(nlg10)。所以总的时间复杂度,是O(nle)与O(nlg10)中较大的哪一个。
    2. 在链接 https://blog.csdn.net/v_july_v/article/details/6685962 中作者总结了各种解法,值得好好看看~~~

    展开全文
  • 高并发,多线程是面试中必不可少至关重要的一环,很关键,相信它会切实的帮到你顺利通过面试
  • 十七道海量数据处理面试题与Bit-map详解。
  • 海量数据处理面试题/大文件问题

    千次阅读 2020-03-20 17:24:06
    面试时,70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都不是。 不要追求难,先看看简单的会不会! 前言 一般而...

    首先引用原博主的一句话,感触颇深

    面试时,70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都不是。

    不要追求难,先看看简单的会不会!

    前言
       一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。

        毕竟受文章和理论之限,本文将摒弃绝大部分的细节,只谈方法/模式论,且注重用最通俗最直白的语言阐述相关问题。最后,有一点必须强调的是,全文行文是基于面试题的分析基础之上的,具体实践过程中,还是得具体情况具体分析,且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。

        OK,若有任何问题,欢迎随时不吝赐教。谢谢。

    何谓海量数据处理?
       所谓海量数据处理,无非就是基于海量数据上的存储、处理、操作。何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。

        那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树,针对空间,无非就一个办法:大而化小,分而治之(hash映射),你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛。

        至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。

        再者,通过本blog内的有关海量数据处理的文章:Big Data Processing,我们已经大致知道,处理海量数据问题,无非就是:

    分而治之/hash映射 + hash统计 + 堆/快速/归并排序;
    双层桶划分
    Bloom filter/Bitmap;
    Trie树/数据库/倒排索引;
    外排序;
    分布式处理之Hadoop/Mapreduce。
        下面,本文第一部分、从set/map谈到hashtable/hash_map/hash_set,简要介绍下set/map/multiset/multimap,及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起,基础最重要),而本文第二部分,则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。

    第一部分、从set/map谈到hashtable/hash_map/hash_set
        稍后本文第二部分中将多次提到hash_map/hash_set,下面稍稍介绍下这些容器,以作为基础准备。一般来说,STL容器分两种,

    序列式容器(vector/list/deque/stack/queue/heap),
    关联式容器。关联式容器又分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表),这些容器均以RB-tree完成。此外,还有第3类关联式容器,如hashtable(散列表),以及以hashtable为底层机制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多键集合)/hash_multimap(散列多键映射表)。也就是说,set/map/multiset/multimap都内含一个RB-tree,而hash_set/hash_map/hash_multiset/hash_multimap都内含一个hashtable。
        所谓关联式容器,类似关联式数据库,每笔数据或每个元素都有一个键值(key)和一个实值(value),即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时,容器内部结构(RB-tree/hashtable)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。

         包括在非关联式数据库中,比如,在MongoDB内,文档(document)是最基本的数据组织形式,每个文档也是以Key-Value(键-值对)的方式组织起来。一个文档可以有多个Key-Value组合,每个Value可以是不同的类型,比如String、Integer、List等等。 
    { "name" : "July",  
      "sex" : "male",  
        "age" : 23 }  

    set/map/multiset/multimap

        set,同map一样,所有元素都会根据元素的键值自动被排序,因为set/map两者的所有各种操作,都只是转而调用RB-tree的操作行为,不过,值得注意的是,两者都不允许两个元素有相同的键值。
        不同的是:set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值,实值就是键值,而map的所有元素都是pair,同时拥有实值(value)和键值(key),pair的第一个元素被视为键值,第二个元素被视为实值。
        至于multiset/multimap,他们的特性及用法和set/map完全相同,唯一的差别就在于它们允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

    hash_set/hash_map/hash_multiset/hash_multimap

        hash_set/hash_map,两者的一切操作都是基于hashtable之上。不同的是,hash_set同set一样,同时拥有实值和键值,且实质就是键值,键值就是实值,而hash_map同map一样,每一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上,所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。
        至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同,唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable(而multiset/multimap,上面说了,底层实现机制是RB-tree),所以它们的元素都不会被自动排序,不过也都允许键值重复。

        所以,综上,说白了,什么样的结构决定其什么样的性质,因为set/map/multiset/multimap都是基于RB-tree之上,所以有自动排序功能,而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上,所以不含有自动排序功能,至于加个前缀multi_无非就是允许键值重复而已。如下图所示:

        此外,

    关于什么hash,请看blog内此篇文章;
    关于红黑树,请参看blog内系列文章,
    关于hash_map的具体应用:请看这里,关于hash_set:请看此文。
        OK,接下来,请看本文第二部分、处理海量数据问题之六把密匙。

    第二部分、处理海量数据问题之六把密匙
    密匙一、分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序
    1、海量日志数据,提取出某日访问百度次数最多的那个IP。
        既然是海量数据处理,那么可想而知,给我们的数据那就一定是海量的。针对这个数据的海量,我们如何着手呢?对的,无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序,说白了,就是先映射,而后统计,最后排序:
    分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
    hash_map统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
    堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。
       具体而论,则是: “首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如%1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map对那1000个文件中的所有IP进行频率统计,然后依次找出各个文件中频率最大的那个IP)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。”--十道海量数据处理面试题与十个方法大总结。

        关于本题,还有几个问题,如下:

          1、Hash取模是一种等价映射,不会存在同一个元素分散到不同小文件中的情况,即这里采用的是mod1000算法,那么相同的IP在hash取模后,只可能落在同一个文件中,不可能被分散的。因为如果两个IP相等,那么经过Hash(IP)之后的哈希值是相同的,将此哈希值取模(如模1000),必定仍然相等。
          2、那到底什么是hash映射呢?简单来说,就是为了便于计算机在有限的内存中处理big数据,从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便是我们通常所说的hash函数,设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置,但数据还是原来的数据,只是代替和表示这些原始数据的形式发生了变化而已。

        OK,有兴趣的,还可以再了解下一致性hash算法,见blog内此文第五部分:http://blog.csdn.net/v_july_v/article/details/6879101。

    2、寻找热门查询,300万个查询字符串中统计最热门的10个查询

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

        解答:由上面第1题,我们知道,数据大则划为小的,如如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。

        但如果数据规模比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。

        所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:

    hash_map统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
    堆排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。所以,我们最终的时间复杂度是:O(N) + N' * O(logK),(N为1000万,N’为300万)。
        别忘了这篇文章中所述的堆排序思路:“维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>...kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现。
        当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

    3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
           由上面那两个例题,分而治之 + hash统计 + 堆/快速排序这个套路,我们已经开始有了屡试不爽的感觉。下面,再拿几道再多多验证下。请看此第3题:又是文件很大,又是内存受限,咋办?还能怎么办呢?无非还是:

    分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
    hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
    堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆)后,再把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
    4、海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
        如果每个数据元素只出现一次,而且只出现在某一台机器中,那么可以采取以下步骤统计出现次数TOP10的数据元素:
    堆排序:在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆,比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大)。
    求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。
        但如果同一个元素重复出现在不同的电脑中呢,如下例子所述:


        这个时候,你可以有两种方法:
    遍历一遍所有数据,重新hash取摸,如此使得同一个元素只出现在单独的一台电脑中,然后采用上面所说的方法,统计每台电脑中各个元素的出现次数找出TOP10,继而组合100台电脑上的TOP10,找出最终的TOP10。
    或者,暴力求解:直接统计统计每台电脑中各个元素的出现次数,然后把同一个元素在不同机器中的出现次数相加,最终从所有数据中找出TOP10。
    5、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。
       方案1:直接上:

    hash映射:顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为a0,a1,..a9)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
    hash_map统计:找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。注:hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
    堆/快速/归并排序:利用快速/堆/归并排序按照出现次数进行排序,将排序好的query和对应的query_cout输出到文件中,这样得到了10个排好序的文件(记为)。最后,对这10个文件进行归并排序(内排序与外排序相结合)。根据此方案1,这里有一份实现:https://github.com/ooooola/sortquery/blob/master/querysort.py。
         除此之外,此题还有以下两个方法:
        方案2:一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。
        方案3:与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

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

        可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

    分而治之/hash映射:遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为,这里漏写个了a1)中。这样每个小文件的大约为300M。遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
    hash_set统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。
        OK,此第一种方法:分而治之/hash映射 + hash统计 + 堆/快速/归并排序,再看最后4道题,如下:

    7、怎么在海量数据中找出重复次数最多的一个?

        方案:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。

    8、上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

        方案:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后利用堆取出前N个出现次数最多的数据。

    9、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        方案1:如果文件比较大,无法一次性读入内存,可以采用hash取模的方法,将大文件分解为多个小文件,对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词,然后再进行归并处理,找出最终的10个最常出现的词。
        方案2:通过hash取模将大文件分解为多个小文件后,除了可以用hash_map统计出每个小文件中10个最常出现的词,也可以用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),最终同样找出出现最频繁的前10个词(可用堆来实现),时间复杂度是O(n*lg10)。
    10. 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

    方案1:这题用trie树比较合适,hash_map也行。
    方案2:from xjbzju:,1000w的数据规模插入操作完全不现实,以前试过在stl下100w元素插入set中已经慢得不能忍受,觉得基于hash的实现不会比红黑树好太多,使用vector+sort+unique都要可行许多,建议还是先hash成小文件分开处理再综合。
        上述方案2中读者xbzju的方法让我想到了一些问题,即是set/map,与hash_set/hash_map的性能比较?共计3个问题,如下:
    1、hash_set在千万级数据下,insert操作优于set? 这位blog:http://t.cn/zOibP7t 给的实践数据可靠不? 
    2、那map和hash_map的性能比较呢? 谁做过相关实验?

    3、那查询操作呢,如下段文字所述?


        或者小数据量时用map,构造快,大数据量时用hash_map?

    rbtree PK hashtable

        据朋友№邦卡猫№的做的红黑树和hash table的性能测试中发现:当数据量基本上int型key时,hash table是rbtree的3-4倍,但hash table一般会浪费大概一半内存。

        因为hash table所做的运算就是个%,而rbtree要比较很多,比如rbtree要看value的数据 ,每个节点要多出3个指针(或者偏移量) 如果需要其他功能,比如,统计某个范围内的key的数量,就需要加一个计数成员。

        且1s rbtree能进行大概50w+次插入,hash table大概是差不多200w次。不过很多的时候,其速度可以忍了,例如倒排索引差不多也是这个速度,而且单线程,且倒排表的拉链长度不会太大。正因为基于树的实现其实不比hashtable慢到哪里去,所以数据库的索引一般都是用的B/B+树,而且B+树还对磁盘友好(B树能有效降低它的高度,所以减少磁盘交互次数)。比如现在非常流行的NoSQL数据库,像MongoDB也是采用的B树索引。关于B树系列,请参考本blog内此篇文章:从B树、B+树、B*树谈到R 树。更多请待后续实验论证。

    11. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。
        方案1:首先根据用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。

    12. 100w个数中找出最大的100个数。
        方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
        方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。
        方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
        接下来,咱们来看第二种方法,双层捅划分。

    密匙二、多层划分
    多层划分----其实本质上还是分而治之的思想,重在“分”的技巧上!
      适用范围:第k大,中位数,不重复或重复的数字
      基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。

    问题实例:

    13、2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
        有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

    14、5亿个int找它们的中位数。

    思路一:这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
    实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
      思路二@绿色夹克衫:同样需要做两遍统计,如果数据存在硬盘上,就需要读取2次。
    方法同基数排序有些像,开一个大小为65536的Int数组,第一遍读取,统计Int32的高16位的情况,也就是0-65535,都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况,因此开一个长度为65536的数组计数就可以。每读取一个数,数组中对应的计数+1,考虑有负数的情况,需要将结果加32768后,记录在相应的数组内。
    第一遍统计之后,遍历数组,逐个累加统计,看中位数处于哪个区间,比如处于区间k,那么0- k-1的区间里数字的数量sum应该<n/2(2.5亿)。而k+1 - 65535的计数和也<n/2,第二遍统计同上面的方法类似,但这次只统计处于区间k的情况,也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿,那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后,再统计一下,看中位数所处的区间,最后将高位和低位组合一下就是结果了。

    密匙三:Bloom filter/Bitmap
    Bloom filter
    关于什么是Bloom filter,请参看blog内此文:

    海量数据处理之Bloom Filter详解
      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
      基本原理及要点:
      对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
      还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
      举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
      注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

      扩展:
      Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

       可以看下上文中的第6题:

    “6、给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

      根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。

        同时,上文的第5题:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。”

    Bitmap
    关于什么是Bitmap,请看blog内此文第二部分:http://blog.csdn.net/v_july_v/article/details/6685962。
        下面关于Bitmap的应用,可以看下上文中的第13题,以及另外一道新题:

    “13、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

        方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
        方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。”

    15、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
        方案1:frome oo,用位图/Bitmap的方法,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

    密匙四、Trie树/数据库/倒排索引
    Trie树

      适用范围:数据量大,重复多,但是数据种类小可以放入内存
      基本原理及要点:实现方式,节点孩子的表示方式
      扩展:压缩实现。
      问题实例:

    上面的第2题:寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
    上面的第5题:有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
    1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
    上面的第8题:一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。其解决方法是:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),然后是找出出现最频繁的前10个词。
        更多有关Trie树的介绍,请参见此文:从Trie树(字典树)谈到后缀树。

    数据库索引
      适用范围:大数据量的增删改查
      基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。

    关于数据库索引及其优化,更多可参见此文:http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html;
    关于MySQL索引背后的数据结构及算法原理,这里还有一篇很好的文章:http://blog.codinglabs.org/articles/theory-of-mysql-index.html;
    关于B 树、B+ 树、B* 树及R 树,本blog内有篇绝佳文章:http://blog.csdn.net/v_JULY_v/article/details/6530142。
    倒排索引(Inverted index)
      适用范围:搜索引擎,关键字查询
      基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
     以英文为例,下面是要被索引的文本:
        T0 = "it is what it is"
        T1 = "what is it"
        T2 = "it is a banana"
        我们就能得到下面的反向文件索引:
        "a":      {2}
        "banana": {2}
        "is":     {0, 1, 2}
        "it":     {0, 1, 2}
        "what":   {0, 1}
     检索的条件"what","is"和"it"将对应集合的交集。

      正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
      扩展:
      问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。

        关于倒排索引的应用,更多请参见:

    第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践,
    第二十六章:基于给定的文档生成倒排索引的编码与实践。

    密匙五、外排序
      适用范围:大数据的排序,去重
      基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
    问题实例:
      1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
      这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1M做hash明显不够,所以可以用来排序。内存可以当输入缓冲区使用。

        关于多路归并算法及外排序的具体应用场景,请参见blog内此文:

    第十章、如何给10^7个数据量的磁盘文件排序

    密匙六、分布式处理之Mapreduce
        MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。但如果你要我再通俗点介绍,那么,说白了,Mapreduce的原理就是一个归并排序。

    适用范围:数据量大,但是数据种类小可以放入内存
    基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
    问题实例:

    The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
    海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
    一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?
        更多具体阐述请参见blog内:

    从Hadhoop框架与MapReduce模式中谈海量数据处理,
    及MapReduce技术的初步了解与学习。
    其它模式/方法论,结合操作系统知识
        至此,六种处理海量数据问题的模式/方法已经阐述完毕。据观察,这方面的面试题无外乎以上一种或其变形,然题目为何取为是:秒杀99%的海量数据处理面试题,而不是100%呢。OK,给读者看最后一道题,如下:
        非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数。
        我们发现上述这道题,无论是以上任何一种模式/方法都不好做,那有什么好的别的方法呢?我们可以看看:操作系统内存分页系统设计(说白了,就是映射+建索引)。
        Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制,这4GB地址空间的一些部分被映射了物理内存,一些部分映射硬盘上的交换文 件,一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存,需要使用物理地址。 关于什么是物理地址和虚拟地址,请看:
    物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上,如果是读,电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写,电路根据这个 地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。 
    虚拟地址 (virtual address): 4G虚拟地址空间中的地址,程序中使用的都是虚拟地址。 使用了分页机制之后,4G的地址空间被分成了固定大小的页,每一页或者被映射到物理内存,或者被映射到硬盘上的交换文件中,或者没有映射任何东西。对于一 般程序来说,4G的地址空间,只有一小部分映射了物理内存,大片大片的部分是没有映射任何东西。物理内存也被分页,来映射地址空间。对于32bit的 Win2k,页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。 
        物理内存分页,一个物理页的大小为4K字节,第0个物理页从物理地址 0x00000000 处开始。由于页的大小为4KB,就是0x1000字节,所以第1页从物理地址 0x00001000 处开始。第2页从物理地址 0x00002000 处开始。可以看到由于页的大小是4KB,所以只需要32bit的地址中高20bit来寻址物理页。 
        返回上面我们的题目:非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数。针对此题,我们可以借鉴上述操作系统中内存分页的设计方法,做出如下解决方案:
        操作系统中的方法,先生成4G的地址表,在把这个表划分为小的4M的小文件做个索引,二级索引。30位前十位表示第几个4M文件,后20位表示在这个4M文件的第几个,等等,基于key value来设计存储,用key来建索引。

        但如果现在只有10000个数,然后怎么去随机从这一万个数里面随机取100个数?请读者思考。更多海里数据处理面试题,请参见此文第一部分:http://blog.csdn.net/v_july_v/article/details/6685962。

    参考文献
    十道海量数据处理面试题与十个方法大总结;
    海量数据处理面试题集锦与Bit-map详解;
    十一、从头到尾彻底解析Hash表算法;
    海量数据处理之Bloom Filter详解;
    从Trie树(字典树)谈到后缀树;
    第三章续、Top K算法问题的实现;
    第十章、如何给10^7个数据量的磁盘文件排序;
    从B树、B+树、B*树谈到R 树;
    第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践;
    第二十六章:基于给定的文档生成倒排索引的编码与实践;
    从Hadhoop框架与MapReduce模式中谈海量数据处理;
    第十六~第二十章:全排列,跳台阶,奇偶排序,第一个只出现一次等问题;
    http://blog.csdn.net/v_JULY_v/article/category/774945;
    STL源码剖析第五章,侯捷著;
    2012百度实习生招聘笔试题:http://blog.csdn.net/hackbuteer1/article/details/7542774;
    Redis/MongoDB绝佳站点:http://blog.nosqlfan.com/;
    国外一面试题网站:http://www.careercup.com/。

    ————————————————
    转载声明:本文为CSDN博主「v_JULY_v」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/v_july_v/article/details/7382693

    展开全文
  • 海量数据处理面试题与相关知识讲解   第一部分 十八道海量数据处理面试题 1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方案1:可以估计每个...

        


    海量数据处理面试题与相关知识讲解



     

    第一部分   十八道海量数据处理面试题


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

    方案1:可以估计每个文件的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

    1. 遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为)中。这样每个小文件的大约为300M。
    2. 遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
    3. 求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

        方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter(关于Bloom filter本blog的后面部分有介绍),如果是,那么该url应该是共同的url(注意会有一定的错误率)。

     

    读者反馈@crowgns:

    1. hash后要判断每个文件大小,如果hash分的不均衡有文件较大,还应继续hash分文件,换个hash算法第二次再分较大的文件,一直分到没有较大的文件为止。这样文件标号可以用A1-2表示(第一次hash编号为1,文件较大所以参加第二次hash,编号为2)
    2. 由于1存在,第一次hash如果有大文件,不能用直接set的方法。建议对每个文件都先用字符串自然顺序排序,然后具有相同hash编号的(如都是1-3,而不能a编号是1,b编号是1-1和1-2),可以直接从头到尾比较一遍。对于层级不一致的,如a1,b有1-1,1-2-1,1-2-2,层级浅的要和层级深的每个文件都比较一次,才能确认每个相同的uri。(说实话,这个第2点我没看太懂)

    2. 有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

    方案1(这个方案不是很好):

    1. 顺序读取10个文件,按照hash(query)的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
    2. 找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。
    3. 这10个文件进行归并排序(内排序与外排序相结合)。

    方案2:

        一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了

    读者反馈@店小二:原文第二个例子中:“找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。”由于query会重复,作为key的话,应该使用hash_multimap 。hash_map 不允许key重复。@hywangw:店小二所述的肯定是错的,hash_map(query,query_count)是用来统计每个query的出现次数又不是存储他们的值出现一次把count+1 就行了 用multimap干什么?多谢hywangw)。

    方案3:

        与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

     

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

        方案:顺序读文件中,对于每个词x,取,然后按照该值存到5000个小文件(记为)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie(关于trie树,请看本blog的后面部分或者我的另外一篇blog)树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。


    4. 海量日志数据,提取出某日访问百度次数最多的那个IP。

        方案1:首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。


    算法思想:分而治之+Hash

    1.IP地址最多有2^32=40G(即使除以8(用bit表示每种情况)也有5G)种取值情况,所以不能完全加载到内存中处理; 
    2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)24值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址; 
    3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
    4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的求最大值的算法得到总体上出现次数最多的IP;

    5. 在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。

        方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32*2bit=1GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

     

    我个人觉得方案1有问题,因为(1)除非你知道这2.5亿个数的范围,否则你是无法采用2-Bitmap映射的;(2)2^32*2bit应该是10GB而不是1GB,而10GB显然是一个承受不起的内存代价。

     

        方案2:也可采用上题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

     

    6、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

        我的第一反应时快速排序+二分查找。以下是其它更好的方法:
        方案1:申请512M(40亿即4G,再除以8)的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。该方案即Bloom filter。

        这个方案有一定的误差。
        方案2:这个问题在《编程珠玑》里有很好的描述(该方案个人认为比较先进),大家可以参考下面的思路,探讨一下:
    又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
    这里我们把40亿个数中的每一个用32位的二进制来表示
    假设这40亿个数开始放在一个文件中。

        然后将这40亿个数分成两类:
          1.最高位为0
          2.最高位为1
        并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
    与要查找的数的最高位比较并接着进入相应的文件再查找

        再然后把这个文件为又分成两类:
          1.次最高位为0
          2.次最高位为1

        并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
        与要查找的数的次最高位比较并接着进入相应的文件再查找。
        .......
        以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。


       附:这里,再简单介绍下,位图方法:
        使用位图法判断整形数组是否存在重复 
        判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。

        位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。


    7. 海量数据分布在100台电脑中,想个办法高效统计出这批数据最大的TOP10。

    方案1:

    1. 在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大。
    2. 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。

    读者反馈@QinLeopard

    第7题的方法中,是不是不能保证每个电脑上的前十条,肯定包含最后频率最高的前十条呢?
    比如说第一个文件中:A(4), B(5), C(6), D(3)
    第二个文件中:A(4),B(5),C(3),D(6)
    第三个文件中: A(6), B(5), C(4), D(3)
    如果要选Top(1), 选出来的结果是A,但结果应该是B。

        @July:我想,这位读者可能没有明确题意。本题目中的TOP10是指最大的10个数,而不是指出现频率最多的10个数。但如果说,现在有另外一题,要你求频率最多的 10个,相当于求访问次数最多的10个IP地址那道题,即是本文中上面的第4题。特此说明。

     

    况且,在找频率最大的TopK时,需要将每个记录放到一个文件中,即全部的A放到一个文件,全部的B放到一个问价,C和D类似。看下面的题:


    8. 怎么在海量数据中找出重复次数最多的一个?

        方案:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求。

     

    9. 上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

        方案:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第7题提到的堆机制完成。


    10. 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

        方案:这题用trie树比较合适,hash_map也应该能行。


    11. 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        方案:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的那一个。


    12. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。

        方案:首先根据词用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。


    13. 100w个数中找出最大的100个数。

    •     方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,直到扫描了所有的元素。复杂度为O(100w*100)。这个方案底层的数据结构还可以用堆来实现,即最小堆。此时的时间复杂度为O(100w*log100),即方案3.
    •     方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,直到比轴大的一部分刚好比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。 (这个很重要),此时得出的前100大元素还是有序的。
    •     方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

    14. 寻找热门查询:

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

    (1) 请描述你解决这个问题的思路;

    (2) 请给出主要的处理流程,算法,以及算法的复杂度。

     

    第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成统计

    第二步、借助堆这个数据结构,找出Top K,时间复杂度为N'*logK。
       即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比,替换。所以,我们最终的时间复杂度是:O(N) + N'*O(logK),(N为1000万,N’为300万)。

    或者:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

     

    备注:按照解法可知,这些记录是可以全部转入内存的。

     

    15. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数中的中位数(按照从小到大排序后中间位置的那个数)?

        方案1:先大体估计一下这些数的范围,比如这里假设这些数都是32位无符号整数(共有2^32个)。我们把0到2^32-1的整数划分为N个范围段,每个段包含(2^32)/N个整数。比如,第一个段为0到2^32/N-1,第二段为(2^32)/N到(2^32)/N-1,…,第N个段为(2^32)(N-1)/N到2^32-1。然后,扫描每个机器上的N个数,把属于第一个区段的数放到第一个机器上,属于第二个区段的数放到第二个机器上,…,属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下面我们依次统计每个机器上数的个数,依次累加,直到找到第k个机器,在该机器上累加的数大于或等于(N^2)/2,而在第k-1个机器上的累加数小于(N^2)/2,并把这个数记为x。那么我们要找的中位数在第k个机器中,排在第(N^2)/2-x位。然后我们对第k个机器的数排序,并找出第(N^2)/2-x个数,即为所求的中位数。复杂度是O(N^2)的。(这个方案比较好)

        方案2:先对每台机器上的数进行排序。排好序后,我们采用归并排序的思想,将这N个机器上的数归并起来得到最终的排序。找到第(N^2)/2个便是所求。复杂度是O(N^2*lgN^2)的。

       方案3:(这个是我加的)将N^2个数依次排开,然后用快速排序的第一趟,找到一个轴,用轴将数组分成两段,在多的那一部分继续上述过程(记少的那部分数的个数为x),此时要找的数在(N^2)/2-x处。然后,再重复上述步骤,直到找到为止。


    16. 最大间隙问题

    给定n个实数,求这n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。

    方案1:最先想到的方法就是先对这n个数据进行排序,然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法:

    1. 找到n个数据中最大和最小数据max和min。
    2. 用n-2个点等分区间[min, max],即将[min, max]等分为n-1个区间(前闭后开区间),将这些区间看作桶,编号为,且桶i 的上界和桶i+1的下届相同,即每个桶的大小相同。每个桶的大小为:。实际上,这些桶的边界构成了一个等差数列(首项为min,公差为),且认为将min放入第一个桶,将max放入第n-1个桶
    3. 将n个数放入n-1个桶中:将每个元素x[i] 分配到某个桶(编号为index),其中,并求出分到每个桶的最大最小数据。
    4. 最大间隙:除最大最小数据max和min以外的n-2个数据放入n-1个桶中,由抽屉原理可知至少有一个桶是空的又因为每个桶的大小相同,所以最大间隙不会在同一桶中出现,一定是某个桶的上界和某个桶的下界之间隙,且该两筒之间的桶一定是空桶。也就是说,最大间隙在桶i的上界和桶j的下界之间产生j>=i+1。一遍扫描即可完成。

     

    17. 将多个集合合并成没有交集的集合

        给定一个字符串的集合,格式如:。要求将其中交集不为空的集合合并,要求合并完成的集合之间无交集,例如上例应输出

    (1) 请描述你解决这个问题的思路;

    (2) 给出主要的处理流程,算法,以及算法的复杂度;

    (3) 请描述可能的改进。

        方案:采用并查集(请查看我的另外一篇关于并查集的blog)。首先所有的字符串都在单独的并查集中。然后依次扫描每个集合,顺序将两个相邻元素合并。例如,对于,首先查看aaa和bbb是否在同一个并查集中,如果不在,那么把它们所在的并查集合并,然后再看bbb和ccc是否在同一个并查集中,如果不在,那么也把它们所在的并查集合并。接下来再扫描其他的集合,当所有的集合都扫描完了,并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话,首先可以记录每个节点的根结点,改进查询。合并的时候,可以把大的和小的进行合,这样也减少复杂度。

     

    18. 最大子序列与最大子矩阵问题

    数组的最大子序列问题:给定一个数组,其中元素有正,也有负,找出其中一个连续子序列,使和最大。

        方案1:这个问题可以动态规划的思想解决。设b[i]表示以第i个元素a[i]结尾的最大子序列,那么显然。基于这一点可以很快用代码实现。(这个思想在编程之美上面也有)

    最大子矩阵问题:给定一个矩阵(二维数组),其中数据有大有小,请找一个子矩阵,使得子矩阵的和最大,并输出这个和。

        方案2:可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素(降维),那么在这个范围内,其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。

     


    第二部分   海量数据处理之Bti-map详解


    什么是Bit-map

        所谓的Bit-map就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

        使用Bitmap排序

        如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

        然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0x01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为1(如下图):

          

    然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:

    然后我们现在遍历一遍Bit区域,将该位是1的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

     

    可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

    问题实例

    1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

        8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)

    2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

        将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map,都是一样的道理(最后一句没看懂)。


     

    第三部分   十个海量数据处理方法大总结


        对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎讨论。

    一、Bloom filter

      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集

      基本原理及要点:
      对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了

      还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

      举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

      注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

    扩展:
      Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

      问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

      根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些url ip是一一对应的,就可以转换成ip,则大大简单了。

    备注: 扩展:bloom filter可以看做是对bit-map的扩展。


    二、Hashing

      适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存

      基本原理及要点:
      hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
      碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

          扩展:
      d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。

      问题实例:
      1).海量日志数据,提取出某日访问百度次数最多的那个IP。

    IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存(真心表示这个有问题,见上面的例子),然后进行统计。


    三、堆

      适用范围:海量数据前n大,并且n比较小,堆可以放入内存

      基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。

      扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数(我表示真心没看懂)。

    问题实例:
       100w个数中找最大的前100个数。
      用一个100个元素大小的最小堆即可。

     

    四、双层桶划分----其实本质上就是【分而治之】的思想,重在“分”的技巧上!

      适用范围:第k大,中位数,不重复或重复的数字
      基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。

      扩展:
      问题实例:
      1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
      有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域再利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

      2).5亿个int找它们的中位数。
      这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

      实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。


    五、数据库索引

      适用范围:大数据量的增删改查

      基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。


    、倒排索引(Inverted index)

      适用范围:搜索引擎,关键字查询

      基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

     以英文为例,下面是要被索引的文本:
        T0 = "it is what it is"
        T1 = "what is it"
        T2 = "it is a banana"

    我们就能得到下面的反向文件索引:

        "a":      {2}
        "banana": {2}
        "is":     {0, 1, 2}
        "it":     {0, 1, 2}
        "what":   {0, 1}

     检索的条件"what","is"和"it"将对应集合的交集。

      正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。

      扩展:
      问题实例:文档检索系统,查询哪些文件包含了某单词,比如常见的学术论文的关键字搜索。


    七、外排序

      适用范围:大数据的排序,去重

      基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树

      扩展:

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

      这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。


    八、trie树

      适用范围:数据量大,重复多,但是数据种类小可以放入内存

      基本原理及要点:实现方式,节点孩子的表示方式

      扩展:压缩实现。

      问题实例:
      1).有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
      2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
      3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。


    九、分布式处理 mapreduce

      适用范围:数据量大,但是数据种类小可以放入内存

      基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

      扩展:
      问题实例:
      1).The canonical example application of MapReduce is a process to count the appearances of
    each different word in a set of documents:
      2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
      3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?


    经典问题分析
      上千万or亿数据(有重复),统计其中出现次数最多的前N个数据,分两种情况:可一次读入内存,不可一次读入。

      可用思路:trie树+堆,数据库索引,划分子集分别统计,hash,分布式计算,近似统计,外排序

      所谓的是否能一次读入内存,实际上应该指去除重复后的数据量。如果去重后数据可以放入内存,我们可以为数据建立字典,比如通过 map,hashmap,trie,然后直接进行统计即可。当然在更新每条数据的出现次数的时候,我们可以利用一个堆来维护出现次数最多的前N个数据,当然这样导致维护次数增加,不如完全统计后在求前N大效率高。

      如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形,可以做的改变就是将字典存放到硬盘上,而不是内存,这可以参考数据库的存储方法。

      当然还有更好的方法,就是可以采用分布式计算,基本上就是map-reduce过程,首先可以根据数据值或者把数据hash(md5)后的值,将数据按照范围划分到不同的机子,最好可以让数据划分后可以一次读入内存,这样不同的机子负责处理各种的数值范围,实际上就是map。得到结果后,各个机子只需拿出各自的出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是reduce过程。

      实际上可能想直接将数据均分到不同的机子上进行处理,这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上,而另一个则可能完全聚集到一个机子上,同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个,我们将1000万的数据分布到10台机器上,找到每台出现次数最多的前 100个,归并之后这样不能保证找到真正的第100个,因为比如出现次数最多的第100个可能有1万个,但是它被分到了10台机子,这样在每台上只有1千个,假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的,比如有1001个,这样本来具有1万个的这个就会被淘汰,即使我们让每台机子选出出现次数最多的1000个再归并,仍然会出错,因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上,而是要根据hash 后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。

       而外排序的方法会消耗大量的IO,效率不会很高。而上面的分布式方法,也可以用于单机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。

       另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际中出现最多的那些词作为一个字典,使得这个规模可以放入内存。

    展开全文
  • 海量数据处理面试题与方法大总结 有任何问题,欢迎指正。谢谢大家
  • 教你如何迅速秒杀掉99的海量数据处理面试题前言何谓海量数据处理第一部分从setmap谈到hashtablehash_maphash_set 第二部分处理海量数据问题之六把密匙密匙一分而治之Hash映射 Hash统计 堆快速归并排序密匙二双层...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,825
精华内容 6,330
关键字:

海量数据处理面试题