Interview_Code
1.0.0
Hier gibt es insgesamt sieben klassische Algorithmusprobleme (ich habe sie in 7 Ordner gesteckt).
Q1 und Q2 sind zwei Themen im Zusammenhang mit der Big -Data -Verarbeitung.
Die anderen fünf Themen sind:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
Hier gibt es sieben klassische Algorithmusprobleme (ich habe sie jeweils in 7 Ordnern gesteckt).
Q1 und Q2 sind zwei Fragen zur Big -Data -Verarbeitung.
Die anderen fünf Fragen sind:
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
Das Folgende ist eine Beschreibung der zugehörigen Dokumente für Q1 und Q2
Im Folgenden finden Sie die relevante Dokumentation für Q1 und Q2
1. Frage Beschreibung.
2. Ideen.
3. Umwelt.
4. Codeausführung.
In den letzten Tagen habe ich Algorithmusingenieure interviewt und zwei besonders gute schriftliche Testfragen gestoßen. Hier sind die Ideen und Codes, die ich eingereicht habe. Sie sind vielleicht nicht die beste Lösung, aber sie sind auch die Ergebnisse meines Studiums und Denkens in den letzten zwei Tagen.
Es ist bekannt, dass eine Tabelle die Anzahl der Likes für jedes Tagebuch aufzeichnet, und verwendet eine Programmiersprache, mit der Sie vertraut sind, um die Anzahl der Likes für das Tagebuch P90 zu berechnen. Definition von P90: Angenommen p90 = n, dann ist die Anzahl der Likes in 90% des Tagebuchs kleiner als oder gleich n. Hinweis: Die ursprünglichen Daten werden nicht sortiert, die Anzahl der Tagebücher erreicht 1 Milliarde
Die Tabellenstruktur lautet wie folgt:
note_id, like_count
1, 4
2, 6
..., ...
Beispiel:
1. Die Anzahl der Likes für 10 Tagebücher beträgt: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, dann P90 = 6
2. Die Anzahl der Klicks für 9 Tagebücher beträgt: 1, 2, 2, 3, 3, 4, 5, 5, 6, dann P90 = 5,5
Eine Datei, die 10 Milliarden Texte enthält, eine pro Zeile, und der Grad jedes Textes überschreitet 1024 nicht, und es kann doppelten Text vorhanden sein. Verwenden Sie die Programmiersprache, mit der Sie vertraut sind, um die meisten 10.000 Texte zu finden. Die Bedingungen sind wie folgt:
1. Keine Duplizierung zwischen Texten.
2. Wenn ein Text im Ergebnis aufbewahrt wird, sollten alle Texte mit dem gleichen Grad wie der Text im Ergebnis beibehalten werden.
Beschreibung: Die externe Sortierung implementiert die Berechnung des p90 -Wertes des Tagebuch -ähnlichen Tabelle
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
Beschreibung: Pandas können Dateien mit <= 5 TB verarbeiten und Pandas direkt verwenden, um super große Dateien zu verarbeiten
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
Beschreibung: Hash -Karte
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
Eingabefunktion: Q1/get_p90.py führt aus:
cd Q1
python get_p90.py
Eingabefunktion: Q2/get_top_1w_pandas.py führt aus:
cd Q2
python get_top_1w_pandas.py
Eingabefunktion: Q2/get_top_1w_hash.py führt aus:
cd Q2
python get_top_1w_hash.py
