Здравствуйте, товарищи!

Я постараюсь пройтись по основным темам/задачам и в коротких видео предоставить необходимый теоретический материал, советы по написанию кода и важные, на мой взгляд, замечания, чтобы вы могли уверенно и успешно проходить такого рода интервью.

0. Friendly SWE Guide Manifesto

У меня есть документ, в котором я собираю дельные советы начинающим программистам. Там про настройку рабочей среды и всего такого. Иногда добавляю туда что-то новенькое. Комментарии приветствуются.

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

Описание задачи: Классический алгоритм поиска элемента в отсортированном массиве за логарифмическое время $O(\log n)$. Разбор фокусируется на правильной работе с границами интервала и избежании переполнения int.

📺 Видео-разбор: Теория и практика
📝 Задача на LeetCode: Binary Search
💡 Мое решение и заметки: Код и замечания
🏠 Домашнее задание: Реализовать поиск самого левого и самого правого вхождения элемента (см. заметки).

2. Быстрое возведение в степень

Описание задачи: Алгоритм вычисления $x^n$ за $O(\log n)$. Обсуждаем рекурсивный и итеративный подходы, а также обработку отрицательных степеней.

📺 Видео-разбор: Теория
📝 Задача на LeetCode: Pow(x, n)
💡 Мое решение и заметки: Иллюстрация алгоритма справа

3. Задача о кузнечике

Описание задачи: Введение в динамическое программирование (одномерный случай). Решаем задачу о количестве способов добраться до ступеньки $n$, прыгая на 1 или 2 шага.

📺 Видео-разбор: Теория
📝 Задача на LeetCode: Climbing Stairs
💡 Мое решение и заметки: Формула и связь с Фибоначчи справа

4. Задача о водопаде (Trapping Rain Water)

Описание задачи: Задача на нахождение объема воды, который может удержаться между столбиками разной высоты. Разбираем эффективный подход с двумя указателями.

📺 Видео-разбор:
- Теория и логика
- Кодинг онлайн
📝 Задача на LeetCode: Trapping Rain Water
💡 Мое решение и заметки: Код и замечания

5. Проверка IP-адреса

Описание задачи: Задача на аккуратную работу со строками и валидацию данных. Проверяем, является ли строка корректным IPv4-адресом.

📺 Видео-разбор: Разбор решения
📝 Задача на LeetCode: Validate IP Address

6. Связные списки (Linked List)

Общая теория: Видео по структурам данных

6.1. Проектирование списка

Описание: Реализация односвязного списка "с нуля". Учимся управлять указателями, добавлять и удалять элементы в разных частях списка.

📝 Задача на LeetCode: Design Linked List
💡 Мое решение и заметки: Имплементация

6.2. Переворот списка

Описание: Классическая задача на изменение направления связей в списке. Разбираем как итеративный, так и рекурсивный способы.

📺 Видео-разбор: Рекурсивный подход
📝 Задача на LeetCode: Reverse Linked List
💡 Мое решение и заметки: Код и замечания

6.3. Цикл в списке

Описание: Определение наличия цикла и нахождение точки входа в цикл.

Наличие цикла (Has Cycle?)
- 📺 Видео-разбор: Алгоритм Флойда
- 📝 Задача на LeetCode: Linked List Cycle
- 💡 Мое решение: Заметки
Точка входа в цикл (Cycle Start Point)
- 📝 Задача на LeetCode: Linked List Cycle II
- 💡 Мое решение: Заметки

6.4. Слияние списков

Описание: Объединение двух отсортированных связных списков в один новый отсортированный список.

📺 Видео-разбор: Кодинг онлайн
📝 Задача на LeetCode: Merge Two Sorted Lists
💡 Мое решение и заметки: Код и замечания

7. Массивы

Общая теория: Видео по работе с массивами

7.1. Пересечение массивов Описание: Нахождение общих элементов в двух массивах. Разбираем подходы с использованием Hash Map и сортировки.
- 📺 Видео-разбор: Логика решения
- 📝 Задача на LeetCode: Intersection of Two Arrays II
- 💡 Мое решение: Python код на GitHub
7.2. k-ая порядковая статистика Описание: Поиск k-го по величине элемента в неотсортированном массиве. Разбираем алгоритм Quick Select со средним временем $O(n)$.
- 📺 Видео-разбор: Quick Select и кучи
- 📝 Задача на LeetCode: Kth Largest Element

8. Перебор (Backtracking)

Описание задачи: Метод поиска решений путем полного перебора вариантов с отсечением неперспективных ветвей. Используется для задач типа "N королев", генерации перестановок или поиска путей в графе.

📺 Видео-разбор:
- Простейший пример
- Перебор на графе

9. Бинарные деревья

Общая теория: Видео по деревьям

9.1. Проверка на BST (Binary Search Tree)

Описание: Проверка того, является ли дерево корректным деревом поиска (для каждого узла все левые потомки меньше, а правые — больше).

📺 Видео-разбор: Разбор и кодинг
📝 Задача на LeetCode: Validate BST
💡 Мое решение и заметки: Код (рекурсия)

9.2. Работа с BST

Описание: Базовые операции in дерево поиска.

Поиск значения в BST
- 📝 Задача на LeetCode: Search in BST
- 💡 Мое решение: Код и заметки
Минимальная разница между узлами
- 📝 Задача на LeetCode: Min Diff in BST
- 💡 Мое решение: Код и заметки

9.3. Наименьший общий предок (LCA)

Описание: Поиск самого "глубокого" узла в дереве, который является предком для двух данных узлов.

📺 Видео-разбор: LCA без предподсчета
📝 Задача на LeetCode: LCA of Binary Tree
🏠 Домашнее задание: LCA of Binary Search Tree

9.4. Десериализация дерева

Описание: Восстановление структуры бинарного дерева по результатам двух его обходов (например, Inorder и Postorder).

📺 Видео-разбор: Inorder + Postorder
📝 Задача на LeetCode: Construct Tree
💡 Мое решение: Код и заметки

10. Бор (Trie)

Описание: Реализация префиксного дерева — структуры данных для эффективного хранения и поиска строк. Незаменим в задачах автодополнения и проверки орфографии.

📺 Видео-разбор: Базовая теория
📝 Задача на LeetCode: Implement Trie

11. Графы

Описание: Основы теории графов: способы представления (матрица смежности, списки смежности) и базовые понятия.

📺 Видео-разбор:
- Определение и примеры
- Способы представления

12. Комбинаторика

Описание: Генерация перестановок. Изучаем алгоритм нахождения следующей в лексикографическом порядке перестановки.

📺 Видео-разбор: Next Permutation
📝 Задача на LeetCode: Next Permutation

13. Два указателя (Two Pointers)

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

13.1. Minimum Window Substring Описание: Поиск кратчайшей подстроки, содержащей все символы заданного набора. Задача на технику "скользящего окна".
- 📺 Видео-разбор: Разбор с кодом
- 📝 Задача на LeetCode: Minimum Window Substring
13.2. Сумма двух элементов Описание: Нахождение в отсортированном массиве двух чисел, сумма которых равна заданному значению.
- 📺 Видео-разбор: Поиск в отсортированном массиве
- 💡 Мое решение: Код

14. Динамическое программирование (Advanced)

Описание: Метод решения сложных задач путем разбиения их на более простые подзадачи с сохранением промежуточных результатов.

14.1. Stock Price Описание: Нахождение максимальной прибыли от покупки и продажи акции.
- 📺 Видео-разбор: Best Time to Buy and Sell Stock
- 📝 Задача на LeetCode: Best Time to Buy and Sell Stock
14.2. Regular Expression Matching Описание: Реализация простейшего парсера регулярок с поддержкой . и *.
- 📺 Видео-разбор: Логика DP
- 📝 Задача на LeetCode: Regular Expression Matching
- 💡 Мое решение: Gist с кодом
14.3. Jump Game II Описание: Нахождение минимального количества прыжков для достижения конца массива. Разбираем через DP и оптимизацию с помощью Segment Tree.
- 📺 Видео-разбор:
  - Теория и оптимизация
  - Кодинг (Segment Tree)
- 📝 Задача на LeetCode: Jump Game II
- 💡 Мое решение: Gist с кодом

15. Разделяй и властвуй

Описание: Стратегия решения задачи путем её рекурсивного разбиения на две или более подзадачи того же типа. Разбираем на примере вычисления всех возможных результатов расстановки скобок в выражении.

📺 Видео-разбор: Different Ways to Add Parentheses
📝 Задача на LeetCode: Different Ways to Add Parentheses

16. Комплексные задачи (Бор + Перебор + ДП)

Описание: Задача про расстановку пробелов в строке (Word Break II). Требует интеграции нескольких подходов для эффективного решения.
📺 Видео-разбор:
- Теория
- Пишу код
📝 Задача на LeetCode: Word Break II
💡 Мое решение: Gist с кодом

Продвинутые и интересные темы

Теория вероятностей

Описание: Разбор нестандартных задач, требующих применения основ теории вероятностей и математического ожидания в контексте программирования.