Учебник Алгоритмы для собеседований для начинающих

Программа курса

1. 1 Сложность и анализ алгоритмов

   1. Что такое big-O и зачем он на собеседовании

      Нотация big-O простыми словами: как оценить рост времени работы алгоритма и почему это первый вопрос интервьюера.

   2. Сложность по памяти и амортизация

      Оценка дополнительной памяти, стек рекурсии и амортизированная сложность на примере динамического массива.

   3. Лучший, средний и худший случай

      Чем отличаются best, average и worst case, и почему интервьюера почти всегда интересует именно худший случай.

2. 2 Массивы, хеши и окна

   1. Два указателя (two pointers)

      Техника двух указателей: как за один проход и O(1) памяти решать задачи на отсортированных массивах. Разбор Two Sum II.

   2. Префиксные суммы

      Префиксные суммы: предподсчёт за O(n) даёт ответы на запросы суммы на отрезке за O(1). Разбор подмассива с заданной суммой.

   3. Хеш-таблицы: Two Sum и частоты

      Хеш-таблицы за O(1): решаем Two Sum за один проход, считаем частоты и группируем анаграммы.

   4. Скользящее окно (sliding window)

      Скользящее окно: как за один проход решать задачи о подстроках и подмассивах. Разбор самой длинной подстроки без повторов.

3. 3 Бинарный поиск, стек и очередь

   1. Бинарный поиск

      Бинарный поиск за O(log n): корректные границы, защита от ошибок на единицу, поиск точной позиции вставки.

   2. Бинарный поиск по ответу

      Бинарный поиск по ответу: когда искомое — не индекс, а число с монотонным свойством. Разбор задачи о минимальной скорости.

   3. Стеки и валидные скобки

      Стек (LIFO): принцип работы и классическая задача проверки правильной скобочной последовательности за O(n).

   4. Очередь и монотонный стек

      Очередь (FIFO) и приём «монотонный стек» для задачи о следующем большем элементе за O(n).

4. 4 Связные списки и деревья

   1. Связный список: разворот

      Односвязный список и его разворот за O(n) и O(1) памяти — одна из самых частых задач на собеседовании.

   2. Цикл в списке: алгоритм Флойда

      Обнаружение цикла в связном списке двумя указателями (черепаха и заяц) за O(n) и O(1) памяти.

   3. Обходы дерева: DFS и BFS

      Бинарное дерево и его обходы: in-order, pre-order, post-order (DFS) и обход по уровням (BFS) с очередью.

5. 5 Рекурсия, backtracking и динамическое программирование

   1. Рекурсия и backtracking: подмножества

      Backtracking на примере генерации всех подмножеств: дерево решений, выбор и откат, сложность O(2^n).

   2. Введение в динамическое программирование

      Динамическое программирование: перекрывающиеся подзадачи и мемоизация на примере чисел Фибоначчи. От O(2^n) к O(n).

   3. DP: монеты, рюкзак и LIS

      Классические задачи DP: размен монетами, рюкзак 0/1 и наибольшая возрастающая подпоследовательность (LIS).

6. 6 Жадность, графы, сортировки и собеседование

   1. Жадные алгоритмы

      Жадные алгоритмы: когда локально оптимальный выбор даёт глобальный оптимум. Разбор задачи о непересекающихся интервалах.

   2. Графы: BFS, DFS и топологическая сортировка

      Представление графа списком смежности, обходы BFS и DFS, топологическая сортировка для задач с зависимостями.

   3. Сортировки: быстрая и слиянием

      Быстрая сортировка и сортировка слиянием: принцип divide and conquer, сложность O(n log n), стабильность и память.

   4. Мета-урок: как пройти собеседование

      Как готовиться к алгоритмическому собеседованию, думать вслух, уточнять условие, оценивать сложность и не паниковать.