https://www.jiuzhang.com/tutorial/big-data-interview-questions
https://www.lintcode.com/ladder/47/
包括哪些方面馒索？
算法：外排序植捎，mapreduce鸣奔，非精確算法，概率算法，hash算法
數(shù)據(jù)結(jié)構(gòu)：hash table，堆，布隆過(guò)濾器种远，位圖
C1 最高頻K項(xiàng)問(wèn)題
主要講了什么?
找出一個(gè)大文件或者數(shù)據(jù)流中出現(xiàn)頻率最高的K項(xiàng)，由是否需要精確和是離線還是在線決定
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
離線算法：
使用快排的算法顽耳，但是要掃兩遍坠敷，無(wú)法滿足數(shù)據(jù)流的算法
使用快選（基于快排的思路）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 練習(xí)地址
https://www.lintcode.com/problem/top-k-largest-numbers/discuss
https://www.jiuzhang.com/solution/top-k-largest-numbers/#tag-highlight-lang-python
從最大K項(xiàng)到最高頻K
先用Hash去存（key, frequency），然后用上面的最小堆的算法
在線算法：
- 低效的算法
所有的整數(shù)都放到堆里面射富，有個(gè)最大堆膝迎，每次取k次最大值，topK
https://www.jiuzhang.com/solution/top-k-largest-numbers/#tag-highlight-lang-python - 高效的算法
維持一個(gè)最小堆
https://www.jiuzhang.com/solution/top-k-largest-numbers-ii/#tag-highlight-lang-python
最高頻K項(xiàng)
https://www.jiuzhang.com/tutorial/big-data-interview-questions/229
一邊計(jì)數(shù)一邊比較TopK
一個(gè)dict計(jì)數(shù)器胰耗，一個(gè)heap(里面存的是(key, count))（最小棧）
取topK限次，直接把這個(gè)heap給變成list
加入新的值，先變dict計(jì)數(shù)器柴灯，然后如果在heap里面卖漫，更新數(shù)組，否則判斷有沒(méi)有滿赠群，沒(méi)有滿也放進(jìn)去羊始，最后判斷新的值是不是比最小棧里面的top（即最小值）大，如果大的話放進(jìn)去
C2 Bloom filter
節(jié)省空間查描，但是存在FP問(wèn)題
- 包含兩個(gè)部分
1.k個(gè)完全獨(dú)立的hash 函數(shù)突委，magic number設(shè)置為31柏卤，37，41等等
magic number不能設(shè)置的太性扔汀（增加碰撞）缘缚，太大（計(jì)算效率低），不是合數(shù)（每一個(gè)大于1的整數(shù)若不是質(zhì)數(shù)钧唐，就會(huì)是合數(shù)
）
2.一個(gè)很大的數(shù)組 - 分為兩種
標(biāo)準(zhǔn)型：HashSet
計(jì)數(shù)型：HashMap
標(biāo)準(zhǔn)型
boolean數(shù)組，k個(gè)哈希值匠襟，k個(gè)有false钝侠，肯定沒(méi)有
如果4個(gè)hash函數(shù)，數(shù)組長(zhǎng)度和要存的個(gè)數(shù)40：1
計(jì)數(shù)型
int數(shù)組酸舍，k個(gè)哈希值帅韧，k個(gè)存的最小為預(yù)估次數(shù)比實(shí)際的數(shù)要大
C3 外排序算法
https://www.cnblogs.com/LUO77/p/5838206.html
大文件分割為小文件，各個(gè)歸并排序
https://leetcode.com/problems/merge-k-sorted-lists/
https://github.com/corvasto/Python-SS
C4 概率類(lèi)的大數(shù)據(jù)問(wèn)題
如何在數(shù)據(jù)流中等概率取出M個(gè)元素
等概率挑出文件中的一行
先選出1行啃勉，剩下的每次能替代的概率是1/k
等概率的挑選Google搜索記錄日志中的一百萬(wàn)條中文搜索記錄
M是出現(xiàn)過(guò)了多少條中文記錄忽舟，N是需要多少條中文記錄
如果buffer不滿先寫(xiě)進(jìn)去，如果滿了淮阐，以N/M的概率隨機(jī)替換原來(lái)的
random.randint(1, M) <= N
