Interview_Code
1.0.0
Здесь есть в общей сложности семь классических проблем алгоритма (я помещаю их в 7 папков);
Q1 и Q2 - это две темы, связанные с обработкой больших данных;
Остальные пять тем:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
Здесь есть семь классических проблем алгоритма (я помещаю их в 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. Примечание: исходные данные не отсортированы, количество дневников достигает 1 миллиарда
Структура таблицы выглядит следующим образом:
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
Файл, который содержит 10 миллиардов текстов, один на строку и степень каждого текста, не превышает 1024, и может быть дублированный текст. Используйте язык программирования, с которым вы знакомы, чтобы найти наиболее 10000 текстов, условия следующие:
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
