6.15 本章习题

本章海量数据的习题

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

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

• 先把100W个关键字hash映射到小文件，根据题意，100W_50B = 50_10^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万人的数据库里，如何在时间０（ｎ）里，找到某个人的十度好友。

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地址相对应的城市，要求有较好的时间复杂度和空间复杂度。