Big Data
1. 访问次数最多的IP
海量日志数据，提取出某日访问百度次数最多的那个IP。
- hashtable统计次数，找到最大。
- 如果内存有限制，按hash(IP)分配到多个文件中处理（同一个IP一定会放在同一个文件中）。求出每个文件中出现次数最多的IP（及其次数）。对多个文件进行合并。
- hashtable用于统计次数的技巧非常常用；但会收到内存容量的限制。常用的结局方式是按hash值写入多个文件中分而治之；然后进行归并。
2. 统计最热门10个查询串
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
- 分而治之，采用hashtable或者trie树对每个小文件中的查询串进行次数统计。
- 采用topK算法，借助一个大小为K的小根堆维护topK元素（这里k = 10），时间复杂度为$$O(NlogK)$$。
- 复习trie树的设计和实现
3. 返回出现次数最高的100个词
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
- 读 -> 分而治之写入文件 -> 每个文件统计次数 -> topK算法遍历所有文件中的所有词，返回top100。
- 文件的个数由数据量和内存限制决定。如果分而治之后单个文件仍然大小仍然超过内存限制，继续分。
4. 对多个文件中query的频度排序
有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
- 解法同前。变化之处在于需要从多个文件中读入query。本质没有变，任然采用hash的方式分配到多个文件中， 对每个文件中的query统计次数并进行排序。（什么方法？给我好好复习下：快速排序，归并排序，堆排序。）排好之后对多个文件进行归并（内排序与外排序相结合）。
- 或者直接hash。（取决于query的重复率）
- MapReduce。（啥？去看看）
5. 找两个文件中共同的url
给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
- 若无内存限制，对a文件建hashtable，然后扫描b文件。
- 若内存有限制，一样对两个文件分别分而治之。把a文件中的url放到1000个新文件中，把b文件中的url放到另外1000个新文件中。（采用同样的hash function保证同一个url对应的新文件编号一样。）然后一一对应处理a和b的子文件。
- Bloom filter?啥？
6. 找不重复整数
在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
- 放到小文件中做。
- bitmap （有意思）
- 基本版是利用一个bit来标记一个整数是否出现。
- 这里需要考虑重复，那么就用两个bit来标记一个整数。（00， 01， 10）
7. 快速判断一个数是否在40亿个数中
给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
- bitmap的基本版。（注意正确估计需要的内存啥的。）
申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
- 如果内存有限制怎么办？根据最高位为0或1进行分类（相当于一个二分法的概念。）
把40亿个数中的每一个用32位的二进制来表示，将这40亿个数按最高位分成两类: 0 vs. 1。并将这两类分别写入到两个文件中。检查待查找的数的最高位并进入相应文件查找。然后根据次高位将数据写入两个文件中......以此类推。时间复杂度为$$O(logN)$$.
- BitMap啥？好好看下
8. 海量数据中找重复次数最多的一个
- hash到小文件，每个小文件求解，再合并。
9.海量数据中统计出现次数最多的前N个数据
上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。
10. 统计词频，求top10
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
- 用trie树统计：时间复杂度是$$O(n*le)$$（$$le$$表示单词的平准长度）。
- 用hashtable统计：时间复杂度是$$O(n)$$.
- 找topK，用堆来实现，时间复杂度是$$O(n*logK)$$。
- 总的时间复杂度是两者中较大的那个。