Interview_Code
1.0.0
There are a total of seven classic algorithm problems here（I put them in 7 folders）;
Q1 and Q2 are two topics related to big data processing;
The other five topics are:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
這裡一共有七道經典的算法題（我把他們分別放在了7個文件夾中）；
Q1和Q2是和大數據處理相關的兩道題目；
其他五道題目分別是：
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
The following is a description of related documents for Q1 and Q2
以下是Q1和Q2的相關文檔說明
一、題目描述.
二、思路.
三、環境.
四、代碼執行.
最近幾天面試算法工程師，遇到兩道特別好的筆試題，這裡是我提交的思路和代碼，可能不是最好的解決方案，但是也這兩天的學習和思考的成果。
已知一張表，記錄了每一篇日記的點贊量，使用你熟悉的編程語言，計算日記的點贊量的P90。 P90的定義:設P90=n，則90%的日記的點贊量，都小於等於n。 注:原始數據未排序，日記量達10億
表結構如下:
note_id, like_count
1, 4
2, 6
..., ...
舉例:
1、10條日記的點贊量分別為:1，2，2，3，3，4，5，5，6，50，則P90 = 6
2、9條日記的點擊量分別為:1，2，2，3，3，4，5，5，6，則P90=5.5
一個文件，其中包含100億條文本，每行一條，每條文本的⻓度不超過1024，可能存在重複文本。 使用你熟悉的編程語言，找到最⻓的1萬條文本，條件如下:
1、文本之間不重複。
2、如果某個文本被保留在結果中，那麼所有與該文本⻓度相同的文本都應該被保留在結果中。
Description: 外部排序實現計算日記點贊表的P90值
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
Description: pandas可以處理<=5TB的文件，直接使用pandas來處理超大文件
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
Description:哈希映射
1.读取大文件表，生成hash key&value 存入1024个小文件（采用桶排序/计数排序，注意value不是字符串内容而是记录所在大文件中的行数）
1.1 key为hash值（采用md5<散列化>）
1.2 value为所在大文件中的行数
2.根据顺序依次从大到小读出topN
3.获取topN在文件中的行数并读取大文件表获取内容
4.循环输出topN
md5码：128位，16个字节
python3.6
pip install tqdm
pip install pandas
入口函數： Q1/get_p90.py執行：
cd Q1
python get_p90.py
入口函數： Q2/get_top_1w_pandas.py執行：
cd Q2
python get_top_1w_pandas.py
入口函數： Q2/get_top_1w_hash.py執行：
cd Q2
python get_top_1w_hash.py
