本文摘要：1.给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件配合的url？方案1：可以预计每个文件安的巨细为50G×64=320G，远远大于内存限制的4G。所以不行能将其完全加载到内存中处置惩罚。 思量接纳分而治之的方法。遍历文件a，对每个url求取 ，然后凭据所取得的值将url划分存储到1000个小文件（记为 ）中。这样每个小文件的约莫为300M。 遍历文件b，接纳和a相同的方式将url划分存储到1000各小文件（记为 ）。

1.给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件配合的url？方案1：可以预计每个文件安的巨细为50G×64=320G，远远大于内存限制的4G。所以不行能将其完全加载到内存中处置惩罚。

思量接纳分而治之的方法。遍历文件a，对每个url求取 ，然后凭据所取得的值将url划分存储到1000个小文件（记为 ）中。这样每个小文件的约莫为300M。

遍历文件b，接纳和a相同的方式将url划分存储到1000各小文件（记为 ）。这样处置惩罚后，所有可能相同的url都在对应的小文件（ ）中，差池应的小文件不行能有相同的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（注意会有一定的错误率）。2.有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你根据query的频度排序。

方案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），最后再举行合并。3.有一个1G巨细的一个文件，内里每一行是一个词，词的巨细不凌驾16字节，内存限制巨细是1M。返回频数最高的100个词。

顺序读文件中，对于每个词x，取 ，然后根据该值存到5000个小文件（记为 ） 中。这样每个文件或许是200k左右。如果其中的有的文件凌驾了1M巨细，还可以根据类似的方法继续往下分，知道剖析获得的小文件的巨细都不凌驾1M。

对 每个小文件，统计每个文件中泛起的词以及相应的频率（可以接纳trie树/hash_map等），并取出泛起频率最大的100个词（可以用含100个结点 的最小堆），并把100词及相应的频率存入文件，这样又获得了5000个文件。下一步就是把这5000个文件举行合并（类似与合并排序）的历程了。4.海量日志数据，提取出某日会见百度次数最多的谁人IP。IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处置惩罚；可以思量接纳分而治之的思想，根据IP地址的Hash(IP) % 1024值，把海量IP日志划分存储到1024个小文件中，这样，每个小文件最多包罗4MB个IP地址；这里解释一下为什么用Hash(IP) % 1024值，如果不用，而直接分类的话，可能会泛起这样一种情况，就是有个IP在每个小文件中都存在，而且这个IP并纷歧定在谁人小文件中是数量最多的，那么最终可能选择的效果会有问题，所以这里用了Hash(IP)%1024值，这样的话，通过盘算IP的Hash值，相同IP肯定会放到一个文件中，固然了差别的IP的Hash值也可能相同，就存在一个小文件中。

对于每一个小文件，可以构建一个IP为key，泛起的次数为value的Hash Map，同时记载当前泛起次数最多的谁人IP地址；可以获得1024个小文件中的泛起次数最多的谁人IP，再依据通例的排序算法得出总体上泛起次数最多的IP。西安尚学堂 http://www.xasxt.com/​Java零基础就业班 最新开班日期：9月中旬上课地址：陕西省西安市高新区科技二路西安软件园天泽大厦五楼咨询电话：029-62258374 QQ 2145598324​​招生工具：1. 零盘算机编程基础学2. 对行业不满足人士3. 跨专业编程喜好者4. 在校大学生实训​Java零基础班，10年 Java 以上开发履历技术讲师、架构师、行业大牛，亲自纯面授课程，手把手教你写编程。

​9月新班免费试听课程已停当，7天免费听课，体验Java兴趣。

本文关键词：亚博yabo888网页登录,西安,尚,学堂,训练,9.5,Java,编程,笔试,面,试题

本文来源：亚博yabo888网页登录-www.ruibaonet.com