本章海量数据的习题

1 有100W个关键字,长度小于等于50字节。用高效的算法找出top10的热词,并对内存的占用不超过1MB。

提示:老题,与caopengcs讨论后,得出具体思路为:

  • 先把100W个关键字hash映射到小文件,根据题意,100W50B = 5010^6B = 50M,而内存只有1M,故干脆搞一个hash函数 % 50,分解成50个小文件;
  • 针对对每个小文件依次运用hashmap(key,value)完成每个key的value次数统计,后用堆找出每个小文件中value次数最大的top 10; -最后依次对每两小文件的top 10归并,得到最终的top 10。

此外,很多细节需要注意下,举个例子,如若hash映射后导致分布不均的话,有的小文件可能会超过1M,故为保险起见,你可能会说根据数据范围分解成50~500或更多的小文件,但到底是多少呢?我觉得这不重要,勿纠结答案,虽准备在平时,但关键还是看临场发挥,保持思路清晰关注细节即可。

2

单机5G内存,磁盘200T的数据,分别为字符串,然后给定一个字符串,判断这200T数据里面有没有这个字符串,怎么做? 如果查询次数会非常的多, 怎么预处理?

提示:如果数据是200g且允许少许误差的话,可以考虑用布隆过滤器Bloom Filter。但本题是200T,得另寻良策,具体解法请读者继续思考。

3

现在有一个大文件,文件里面的每一行都有一个group标识(group很多,但是每个group的数据量很小),现在要求把这个大文件分成十个小文件,要求:

  • 1、同一个group的必须在一个文件里面;
  • 2、切分之后,要求十个小文件的数据量尽可能均衡。

7

服务器内存1G,有一个2G的文件,里面每行存着一个QQ号(5-10位数),怎么最快找出出现过最多次的QQ号。

8

尽量高效的统计一片英文文章(总单词数目)里出现的所有英文单词,按照在文章中首次出现的顺序打印输出该单词和它的出现次数。

9

在人人好友里,A和B是好友,B和C是好友,如果A 和C不是好友,那么C是A的二度好友,在一个有10万人的数据库里,如何在时间0(n)里,找到某个人的十度好友。

12

海量记录,记录形式如下: TERMID URLNOCOUNT urlno1 urlno2 ..., urlnon,请问怎么考虑资源和时间这两个因素,实现快速查询任意两个记录的交集,并集等,设计相关的数据结构和算法。

14

有一亿个整数,请找出最大的1000个,要求时间越短越好,空间占用越少越好。

18

10亿个int型整数,如何找出重复出现的数字。

19

有2G的一个文本文档,文件每行存储的是一个句子,每个单词是用空格隔开的。问:输入一个句子,如何找到和它最相似的前10个句子。

提示:可用倒排文档。

20

某家视频网站,每天有上亿的视频被观看,现在公司要请研发人员找出最热门的视频。 该问题的输入可以简化为一个字符串文件,每一行都表示一个视频id,然后要找出出现次数最多的前100个视频id,将其输出,同时输出该视频的出现次数。

  • 1.假设每天的视频播放次数为3亿次,被观看的视频数量为一百万个,每个视频ID的长度为20字节,限定使用的内存为1G。请简述做法,再写代码。
  • 2.假设每个月的视频播放次数为100亿次,被观看的视频数量为1亿,每个视频ID的长度为20字节,一台机器被限定使用的内存为1G。

提示:万变不离其宗,分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序。

21

有一个log文件,里面记录的格式为:

QQ号     时间        flag

123456   14:00:00     0 

123457   14:00:01     1

其中flag=0表示登录 flag=1表示退出

问:统计一天平均在线的QQ数。

22

一个文本,一万行,每行一个词,统计出现频率最高的前10个词(词的平均长度为Len)。并分析时间复杂度。

23

在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可。

24

一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空,这两种情形都定义为null。这样构成一个单链表。给两条这样单链表,判断里面是否存在同样的url。url以亿级计,资源不足以hash。

25

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

26

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

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

28

现有一200M的文本文件,里面记录着IP地址和对应地域信息,如

202.100.83.56 北京 北京大学

202.100.83.120 北京 人民大学

202.100.83.134 北京 中国青年政治学院

211.93.120.45 长春市 长春大学

211.93.120.129 吉林市 吉林大学

211.93.120.200 长春 长春KTV

现有6亿个IP地址,请编写程序,读取IP地址便转换成IP地址相对应的城市,要求有较好的时间复杂度和空间复杂度。