Interview_Code
1.0.0
Aquí hay un total de siete problemas de algoritmo clásico (los pongo en 7 carpetas);
Q1 y Q2 son dos temas relacionados con el procesamiento de big data;
Los otros cinco temas son:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
Aquí hay siete problemas de algoritmos clásicos (los pongo en 7 carpetas respectivamente);
Q1 y Q2 son dos preguntas relacionadas con el procesamiento de big data;
Las otras cinco preguntas son:
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
La siguiente es una descripción de documentos relacionados para Q1 y Q2
Las siguientes son la documentación relevante para Q1 y Q2
1. Descripción de la pregunta.
2. Ideas.
3. Medio ambiente.
4. Ejecución del código.
En los últimos días, entrevisté a los ingenieros de algoritmo y encontré dos preguntas de prueba escrita particularmente buenas. Aquí están las ideas y códigos que presenté. Puede que no sean la mejor solución, pero también son los resultados de mi estudio y pensamiento en los últimos dos días.
Se sabe que una tabla registra el número de me gusta para cada diario, y utiliza un lenguaje de programación con el que está familiarizado para calcular la cantidad de me gusta para el diario P90. Definición de P90: Suponga P90 = N, entonces el número de me gusta en el 90% del diario es menor o igual a N. Nota: Los datos originales no están ordenados, el número de diarios alcanza los mil millones
La estructura de la tabla es la siguiente:
note_id, like_count
1, 4
2, 6
..., ...
Ejemplo:
1. El número de me gusta para 10 diarios es: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, luego P90 = 6
2. El número de clics para 9 diarios es: 1, 2, 2, 3, 3, 4, 5, 5, 6, luego P90 = 5.5
Un archivo que contiene 10 mil millones de textos, uno por línea, y el grado de cada texto no excede 1024, y puede haber texto duplicado. Use el lenguaje de programación con el que está familiarizado para encontrar la mayor cantidad de 10,000 textos, las condiciones son las siguientes:
1. Sin duplicación entre textos.
2. Si un texto se retiene en el resultado, entonces todos los textos con el mismo grado que el texto debe retenirse en el resultado.
Descripción: Clasificación externa implementa el cálculo del valor P90 del diario como la tabla
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
Descripción: Los pandas pueden procesar archivos con <= 5tb y usar pandas directamente para procesar archivos súper grandes
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
Descripción: mapa hash
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
Función de entrada: Q1/get_p90.py se ejecuta:
cd Q1
python get_p90.py
Función de entrada: Q2/get_top_1w_pandas.py ejecuta:
cd Q2
python get_top_1w_pandas.py
Función de entrada: Q2/get_top_1w_hash.py ejecuta:
cd Q2
python get_top_1w_hash.py
