Топ алгоритмов на собесе

Этот список был собран из большого опыта прохождения coding life interview в разные компании.
Конечно сложность алгоритмов зависит от направления. Мы рассмотрим три самых популярных направления: Backend, ML, Аналитика.

Backend
1) Префиксная сумма и два указателя.
Очень часто встречается, как первая задача на собесе.
2) Задачи, которые решаются Hash-map.
В основном - это задачи где можно снизить асимптотику до O(N).
3) BFS, DFS.
В качестве графа обычно дают дерево.
4) Двоичное дерево.
Чаще этот алгоритм встречается в качестве второй задачи.
5) Кратчайшие пути.
Топологическая сортировка графа, Дейкстра, Флойд.
6) Жадные алгоритмы.
Задачи на эту тему дают достаточно простые, но с подводными камнями.

1, 2, 6 алгоритмы обычно дают в качестве первой задачи, но не стоит недооценивать эти темы. Например у людей в задаче на два указателя возникают проблемы с индексами, а в жадном алгоритме не могут доказать корректность алгоритма.
В качестве второй задачи предпочитают давать задачи на графы и структуры данных параллельно спрашиваю теорию и свойства структур.

ML
1) Двоичное дерево
2) Нахождения кратчайших путей в графе.
Обычно это алгоритм Дейкстры или Флойд.
3) Обходы графа BFS, DFS.
4) Hash-map
5) Динамическое программирование.
Чаще всего просят написать простенькую дп для подсчета вероятности

В ML меньше алгособесов и чаще дают алгоритмы на графы и структуры данных. Будьте готовы к тому, что у вас будут спрашивать свойства и теорию.
В отличие от бэкенда у вас будет в два раза меньше алгоритмов, а больше вопросов по классическому мл.

Аналитика
1) Простые задачи связанные с массивами, строками, математикой.
Обычно вас просят распарсить строку, посчитать в массиве количество каких то элементов.
2) Hash-map
3) Префиксные суммы
4) Жадные алгоритмы.

В аналитеке алгоритмы полегче и часто дают простенькую задачу, чтобы проверить умения кодинга.
На лайв кодинге аналитикам больше дают задачи по математике, статистики, скл и подобный стек с литкода уровня изи-медиум.

На любом алгоритмическом собеседовании вам точно зададут вопрос о том, какая асимптотика вашего алгоритма и почему. Чаще всего неправильно отвечают люди, которые пишут на питоне. Например используют срезы, не зная за сколько они работают и в результате неправильно оценивают асимптотику.

Практически во всех life coding interview не любят давать задачи с асимптотикой O(n^2). Например в Яндексе за последние три года я не встретил ни одну задачу, которая решалась бы за O(n^2).
Наиболее распространенные задачи, как правило, требуют O(n) времени в исключительных случаях O(n logn). Используйте это наблюдение для более эффективного распределения времени на подготовку.

Если вы решили подтянуть эти темы я вам рекомендую изучать в таком порядке.

Префиксные суммы, Бинарный поиск, Hash-map, два указателя.
BFS DFS, Дейкстра, Флойд, Двоичное дерево.
Жадные алгоритмы, динамическое программирование.
Все эти темы мы отработаем на огромном количестве примеров, пройдя наш курс, вы станете настоящим мастером спорта по алгоритмам😎

Для лучшего понимания этих тем хорошо подойдет сайт визуализации алгоритмов. Особенно поможет новичкам лучше понять структуры данных и графы.