简述 hadoop 怎么样实现二级排序？
在Reduce阶段，先对Key排序，再对Value排序
最常用的方法是将Value放到Key中，实现一个组合Key，然后自定义Key排序规则(为Key实现一个WritableComparable)
如何使用MapReduce实现两个表join，可以考虑一下几种情况:(1)一个表大，一个表小(可放到内存中) (2)两个表都是大表
第一种情况比较简单，只需将小表放到DistributedCache中即可；
第二种情况常用的方法有：map-side join(要求输入数据有序，通常用户Hbase中的数据表连接)，reduce-side join，semi join(半连接)
给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？
方案 1：将大文件分成能够被内存加载的小文件。
可以估计每个文件安的大小为 50G×64=320G，远远大于内存限制的 4G。
所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
s遍历文件a，对每个url求取 ，然后根据所取得的值将url分别存储到 1000 个小文件(记为)中
这样每个小文件的大约为300M。
s遍历文件b，采取和a相同的方式将url分别存储到1000各小文件(记为)
这样处理后，所有可能相同的url都在对应的小文件()中，不对应的小文件不可能有相同的url
然后我们只要求出1000对小文件中相同的url即可
s 求每对小文件中相同的url时，可以把其中一个小文件的url存储到 hash_set中
然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，
如果是，那么就是共同的url，存到文件里面就可以了。
方案 2：内存映射成 BIT 最小存储单元。
如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit
将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，
检查是否与Bloom filter，如果是，那么该 url 应该是共同的 url(注意会有一定的错误率)。
有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序
方案 1：
s顺序读取10个文件，按照 hash(query)%10 的结果将 query 写入到另外10个文件(记为)中
这样新生成的文件每个的大小大约也1G(假设 hash 函数是随机的)
s找一台内存在2G左右的机器，依次对用hash_map(query,query_count)来统计每个query出现的次数。
利用快速/堆/归并排序按照出现次数进行排序。
将排序好的 query 和对应的 query_cout 输出到文件中。
这样得到了 10 个排好序的文件(记为)
s 对 这 10 个文件进行归并排序(内排序与外排序相结合)
方案 2：
一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了
这样，我们就可以采用 trie树/hash_map 等直接来统计每个 query 出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
方案 3：
与方案1类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，
采用分布式的架构来处理（比如 MapReduce），最后再进行合并。
//一般在大文件中找出出现频率高的，先把大文件映射成小文件，模 1000，在小文件中找到高频的
有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词
方案 1：
顺序读文件中，对于每个词x,取 ，然后按照该值存到5000个小文件(记为 )中。
这样每个文件大概是 200k 左右。
如果其中的有的文件超过了 1M 大小，还可以按照类似的方法继续往下分
知道分解得到的小文件的大小都不超过 1M。
对每个小文件，统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等)，
并取出出现频率最大的100个词(可以用含100个结 点的最小堆)，
并把100词及相应的频率存入文件，这样又得到了 5000 个文件。
下一步就是把这 5000 个文件进行归并(类似与归并排序)的过程了。
方案2:
1 将文件逐行读写到另一个文件中，并将每行单词全变成小写
2 十六次循环执行，将每行单词按照a-z写到不同文件里
3 最后相同的单词都写在了通一个文件里
4 再将文件读写到各自另一个文件里，内容是“单词 个数”
5 定义一个treemap，大小是100，依次插入大的，移除小的
6 最后得出结果
海量日志数据，提取出某日访问百度次数最多的那个 IP
1 先根据日期在日志文件中提取出ip，根据ip哈希进行分写N个文件。
2 采用mapreduce的word cont
方案 1：
首先是这一天，并且是访问百度的日志中的 IP 取出来，逐个写入到一个大文件中。
注意到 IP是 32 位的，最多有 个 IP。同样可以采用映射的方法，比如模 1000，
把整个大文件映射为1000个小文件，
再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计，然后再找出频率最大的几个)及相应的频率。
然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
在 2.5 亿个整数中找出不重复的整数，内存不足以容纳这 2.5 亿个整数
方案 1：
采用 2-Bitmap(每个数分配 2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行，
共需内存 内存，还可以接受。
然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，
如果是00变 01，01变10，10保持不变。
所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。
方案 2：
也可采用上题类似的方法，进行划分小文件的方法
然后在小文件中找出不重复的整数，并排序
然后再进行归并，注意去除重复的元素。
方案3：
1 将2.5亿个整数重写到一个文件里，内个整数占一行。
2 进行对半排序重写到新的文件里，这样最后2.5亿个整数在文件里便是有序的了
3 读取文本，将不重复的写到一个新的文件里即可。
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析
方案 1：
这题是考虑时间效率。用trie 树统计每个词出现的次数，时间复杂度是 O(n*le)(le表示单词的平准长度)
然后是找出出现最频繁的前 10 个词，可以用堆来实现，时间复杂度是 O(n*lg10)。
所以总的时间复杂度，是 O(n*le)与 O(n*lg10)中较大的哪一个
