https://www.jiuzhang.com/tutorial/big-data-interview-questions
https://www.lintcode.com/ladder/47/
包括哪些方面？
算法：外排序，mapreduce，非精确算法，概率算法，hash算法
数据结构：hash table，堆，布隆过滤器，位图
C1 最高频K项问题
主要讲了什么?
找出一个大文件或者数据流中出现频率最高的K项，由是否需要精确和是离线还是在线决定
K Closest Points
https://www.lintcode.com/problem/k-closest-points/description?_from=ladder&&fromId=47
https://www.lintcode.com/problem/k-closest-points/discuss?_from=ladder&&fromId=47
离线算法：
使用快排的算法，但是要扫两遍，无法满足数据流的算法
使用快选（基于快排的思路）O（N）
https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60306/Python-different-solutions-with-comments-(bubble-sort-selection-sort-heap-sort-and-quick-sort).
基于堆 O(klogN)
LintCode 练习地址
https://www.lintcode.com/problem/top-k-largest-numbers/discuss
https://www.jiuzhang.com/solution/top-k-largest-numbers/#tag-highlight-lang-python
从最大K项到最高频K
先用Hash去存（key, frequency），然后用上面的最小堆的算法
在线算法：
- 低效的算法
所有的整数都放到堆里面，有个最大堆，每次取k次最大值，topK
https://www.jiuzhang.com/solution/top-k-largest-numbers/#tag-highlight-lang-python - 高效的算法
维持一个最小堆
https://www.jiuzhang.com/solution/top-k-largest-numbers-ii/#tag-highlight-lang-python
最高频K项
https://www.jiuzhang.com/tutorial/big-data-interview-questions/229
一边计数一边比较TopK
一个dict计数器，一个heap(里面存的是(key, count))（最小栈）
取topK，直接把这个heap给变成list
加入新的值，先变dict计数器，然后如果在heap里面，更新数组，否则判断有没有满，没有满也放进去，最后判断新的值是不是比最小栈里面的top（即最小值）大，如果大的话放进去
C2 Bloom filter
节省空间，但是存在FP问题
- 包含两个部分
1.k个完全独立的hash 函数，magic number设置为31，37，41等等
magic number不能设置的太小（增加碰撞），太大（计算效率低），不是合数（每一个大于1的整数若不是质数，就会是合数
）
2.一个很大的数组 - 分为两种
标准型：HashSet
计数型：HashMap
标准型
boolean数组，k个哈希值，k个有false，肯定没有
如果4个hash函数，数组长度和要存的个数40：1
计数型
int数组，k个哈希值，k个存的最小为预估次数比实际的数要大
C3 外排序算法
https://www.cnblogs.com/LUO77/p/5838206.html
大文件分割为小文件，各个归并排序
https://leetcode.com/problems/merge-k-sorted-lists/
https://github.com/corvasto/Python-SS
C4 概率类的大数据问题
如何在数据流中等概率取出M个元素
等概率挑出文件中的一行
先选出1行，剩下的每次能替代的概率是1/k
等概率的挑选Google搜索记录日志中的一百万条中文搜索记录
M是出现过了多少条中文记录，N是需要多少条中文记录
如果buffer不满先写进去，如果满了，以N/M的概率随机替换原来的
random.randint(1, M) <= N
