Топ теор вопросов на лайв кодинге

Список основан на на моем опыте и опыте коллег проведения собесов. Свежие задачи с собесов выкладываются здесь.

1. Сложность алгоритма
Кроме алгоритмов, мы часто применяем встроенные функции, такие как max(arr). Многие не знают временную сложность этих функций, что может привести к неправильной оценке времени. Для заполнения пробелов в знаниях рекомендуется изучать документацию по функциям и смотреть шпаргалку.

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

2. Структуры данных
Разница между двоичным деревом и сбалансированным двоичным деревом (Почему то многие думают, что деревья бывают только двоичные).
Для лучшего понимания разницы рекомендую почитать статью.

AVL - дерево - сбалансированное двоичное дерево поиска. Про AVL речь точно зайдет если начнут спрашивать балансировку двоичного дерева.

С++:
Необходимо глубоко понимать внутреннее устройство контейнеров, таких как vector, deque, stack и другие. Например, часто встречаются вопросы о том, почему операция push_back в векторе выполняется за O(1), и как происходит выделение памяти.

Обязательно посмотрите какие алгоритмы реализованы под капотом - это очень важно, например map написан на красно-черных деревьях.

Время работы вставки, удаления вы должны знать наизусть, понимать разницу между set, multiset а также map с unordered_map.

Python.
Вероятно, вас могут спросить о том, как управляется память, сколько времени занимает операция append в списке, какова разница между контейнерами set и heap, а также о времени работы словаря (dict).

Часто встречаемой ошибкой является предположение, что элементы в контейнере set всегда упорядочены. Это верно в случае C++, но не совсем верно для Python из-за чего особенно важно знать, что происходит "под капотом".

3. Графы и деревья

Термины
Чтобы говорить на одном языке с собеседующим вам нужно разобрать в терминах. (Действительно если вы будете спрашивать, что такое компонента графа в глазах собеседующего это очень плохо)

Хранения графа
Перед кодингком вам спросят, как вы собираетесь хранить граф. Почему именно этот способ выбрали и в чем отличие от других видов хранения графов. Например матрицу смежности использует при полных графах, а список смежности, когда количество ребер сильно меньше чем O(n^2).

Еще одна распространенная ошибка говорить, что обходы графов (BFS, DFS) работают за O(n), а не за O(n + m).
На эту ошибку могут закрыть глаза или же собеседующий будет наталкивать на правильный ответ в духе: " рассмотрим граф в котором ребер сильно больше чем вершин, разве за O(n) будет работать обход ?". В общем просто теряете время, чего у вас и так мало.

Дейкстра
В каких графах не будет работать алгоритм Дейкстры ?
-Если в графе есть отрицательный цикл алгоритм Дейкстры уйдет в бесконечный цикл.
Как узнать есть ли в графе отрицательный цикл ?
-Алгоритм Форда Беллмана.
В чем разница между алгоритмом Флойда и Дейсктры?
-Флойд находит кратчайшие расстояние между всеми парами вершин, а Дейкстра от одной до всех остальных.
Почему бы тогда не запустить алгоритм Дейкстры от каждой вершины вместо использования алгоритма Флойда ?
-Потому, что асимптотически Флойд будет работать быстрее.

4. Дп и жадные алгоритмы
Объясните концепцию динамического программирования, что такое жадный алгоритм, в чем разница между динамическим программированием и жадным алгоритмом, в каких случаях жадные алгоритмы не дают оптимального решения.
Это типичные вопросы когда встречается задача на дп.
Вы должны понимать, что жадный алгоритм устроен на какой-то стратегии и вы должны доказывать вашу стратегию, например тот же алгоритм Дейкстры.
Или та же задача про рюкзак, которая решается динамическим программированием. Любое жадное решение будет решать задачу только приближенно..
Отличной практикой является открывать задачи на динамическое программирование и пытаться их решить жадным способом, так вы будете понимать класс задач которые решают дп.

Чтобы без труда отвечать на такие вопросы, советую на наш курс.