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