Interview_Code
1.0.0
Há um total de sete problemas clássicos de algoritmo aqui (eu os coloquei em 7 pastas);
Q1 e Q2 são dois tópicos relacionados ao processamento de big data;
Os outros cinco tópicos são:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
Existem sete problemas clássicos de algoritmo aqui (eu os coloquei em 7 pastas, respectivamente);
Q1 e Q2 são duas perguntas relacionadas ao processamento de big data;
As outras cinco perguntas são:
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
A seguir, é apresentada uma descrição dos documentos relacionados para Q1 e Q2
A seguir estão a documentação relevante para o primeiro trimestre e o Q2
1. Descrição da pergunta.
2. Ideias.
3. Ambiente.
4. Execução de código.
Nos últimos dias, entrevistei engenheiros de algoritmos e encontrei duas perguntas particularmente boas de teste por escrito. Aqui estão as idéias e códigos que enviei. Eles podem não ser a melhor solução, mas também são os resultados do meu estudo e do pensamento nos últimos dois dias.
Sabe -se que uma tabela registra o número de curtidas para cada diário e usa uma linguagem de programação com a qual você está familiarizado para calcular o número de curtidas para o diário P90. Definição de P90: Suponha que p90 = n, então o número de curtidas em 90% do diário é menor ou igual a n. Nota: Os dados originais não são classificados, o número de diários atinge 1 bilhão
A estrutura da tabela é a seguinte:
note_id, like_count
1, 4
2, 6
..., ...
Exemplo:
1. O número de curtidas para 10 diários é: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, depois P90 = 6
2. O número de cliques para 9 diários é: 1, 2, 2, 3, 3, 4, 5, 5, 6, depois p90 = 5.5
Um arquivo que contém 10 bilhões de textos, um por linha e o grau de cada texto não excede 1024, e pode haver texto duplicado. Use a linguagem de programação com a qual você está familiarizado para encontrar o máximo de 10.000 textos, as condições são as seguintes:
1. Sem duplicação entre textos.
2. Se um texto for retido no resultado, todos os textos com o mesmo grau que o texto devem ser retidos no resultado.
Descrição: Classificação externa implementa o cálculo do valor p90 do diário como a tabela
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
Descrição: Os pandas podem processar arquivos com <= 5tb e usar pandas diretamente para processar arquivos super grandes
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
Descrição: Mapa de 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
Função de entrada: Q1/get_p90.py Executa:
cd Q1
python get_p90.py
Função de entrada: Q2/get_top_1w_pandas.py Executa:
cd Q2
python get_top_1w_pandas.py
Função de entrada: Q2/get_top_1w_hash.py Executa:
cd Q2
python get_top_1w_hash.py
