Interview_Code
1.0.0
Il y a un total de sept problèmes d'algorithmes classiques ici (je les ai mis dans 7 dossiers);
Les Q1 et Q2 sont deux sujets liés au traitement des mégadonnées;
Les cinq autres sujets sont:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
Il y a sept problèmes d'algorithmes classiques ici (je les ai mis dans 7 dossiers respectivement);
Les Q1 et Q2 sont deux questions liées au traitement des mégadonnées;
Les cinq autres questions sont:
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
Ce qui suit est une description des documents connexes pour les Q1 et Q2
Voici la documentation pertinente pour les Q1 et Q2
1. Description de la question.
2. Idées.
3. Environnement.
4. Exécution de code.
Au cours des derniers jours, j'ai interviewé des ingénieurs d'algorithmes et rencontré deux questions de test écrites particulièrement bonnes. Voici les idées et les codes que j'ai soumis. Ils ne sont peut-être pas la meilleure solution, mais ce sont également les résultats de mon étude et de la réflexion au cours des deux derniers jours.
Une table est connue pour enregistrer le nombre de likes pour chaque journal et utilise un langage de programmation que vous connaissez pour calculer le nombre de likes pour le journal P90. Définition de P90: Supposons P90 = N, alors le nombre de likes dans 90% du journal est inférieur ou égal à n. Remarque: les données d'origine ne sont pas triées, le nombre de journaux atteint 1 milliard
La structure du tableau est la suivante:
note_id, like_count
1, 4
2, 6
..., ...
Exemple:
1. Le nombre de goûts pour 10 journaux est: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, puis P90 = 6
2. Le nombre de clics pour 9 journaux est: 1, 2, 2, 3, 3, 4, 5, 5, 6, puis P90 = 5,5
Un fichier qui contient 10 milliards de textes, un par ligne, et le degré de chaque texte ne dépasse pas 1024, et il peut y avoir du texte en double. Utilisez le langage de programmation que vous connaissez pour trouver le plus de 10 000 textes, les conditions sont les suivantes:
1. Pas de duplication entre les textes.
2. Si un texte est conservé dans le résultat, tous les textes ayant le même degré que le texte doivent être conservés dans le résultat.
Description: Le tri externe implémente le calcul de la valeur P90 du Table du journal
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
Description: les pandas peuvent traiter les fichiers avec <= 5tb et utiliser des pandas directement pour traiter les fichiers super volumineux
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
Description: Carte de hachage
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
Fonction d'entrée: Q1/get_p90.py exécute:
cd Q1
python get_p90.py
Fonction d'entrée: Q2/get_top_1w_pandas.py exécute:
cd Q2
python get_top_1w_pandas.py
Fonction d'entrée: Q2/get_top_1w_hash.py exécute:
cd Q2
python get_top_1w_hash.py
