Interview_Code
1.0.0
여기에는 총 7 개의 고전적인 알고리즘 문제가 있습니다 (나는 7 개의 폴더에 넣습니다).
Q1과 Q2는 빅 데이터 처리와 관련된 두 가지 주제입니다.
다른 5 가지 주제는 다음과 같습니다.
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
여기에는 7 가지 고전적인 알고리즘 문제가 있습니다 (각각 7 개의 폴더에 넣습니다).
Q1과 Q2는 빅 데이터 처리와 관련된 두 가지 질문입니다.
다른 다섯 가지 질문은 다음과 같습니다.
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
다음은 Q1 및 Q2의 관련 문서에 대한 설명입니다.
다음은 Q1 및 Q2의 관련 문서입니다.
1. 질문 설명.
2. 아이디어.
3. 환경.
4. 코드 실행.
지난 며칠 동안, 나는 알고리즘 엔지니어를 인터뷰했으며 두 가지 좋은 필기 시험 질문을 만났습니다. 내가 제출 한 아이디어와 코드는 다음과 같습니다. 그것들은 최선의 해결책이 아닐 수도 있지만 지난 이틀 동안 내 연구와 사고의 결과이기도합니다.
테이블은 각 일기에 대해 좋아하는 수를 기록하는 것으로 알려져 있으며, 친숙한 프로그래밍 언어를 사용하여 일기 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 억 개의 텍스트, 한 줄 당 1 개 및 각 텍스트의 정도가 1024를 초과하지 않으며 중복 텍스트가있을 수 있습니다. 익숙한 프로그래밍 언어를 사용하여 가장 10,000 개의 텍스트를 찾으십시오. 조건은 다음과 같습니다.
1. 텍스트 간의 중복이 없습니다.
2. 결과에 텍스트가 유지되면 텍스트와 동일한 정도의 모든 텍스트를 결과에서 유지해야합니다.
설명 : 외부 분류 구현 테이블과 같은 일기의 p90 값 계산
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
설명 : 팬더는 <= 5TB로 파일을 처리하고 팬더를 직접 사용하여 대형 파일을 처리 할 수 있습니다.
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
설명 : 해시 맵
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
