Алгоритмы и структуры данных

Принцип: учим паттерны, а не количество задач. Освоив паттерн, решаешь десятки похожих задач (Habr: подготовка к алго-собесу в Яндексе). Язык решений — Swift, с заметками про подводные камни онлайн-редактора без автодополнения.

Как устроен курс

Каждый модуль = теория → паттерн → разобранный пример → задачи для закрепления → видео/материалы. Ключевая методика (из разбора реального собеса в Яндексе):

• Готовиться по темам/паттернам, не прорешивать всё подряд.
• На задачу — до 30 минут самостоятельно, потом подсказка/идея (без готового кода).
• Интервальное повторение: вернуться к теме через несколько дней.
• Вести дневник ошибок.
• «Компилятор в голове» — критически перечитать код перед сдачей.
• Мок-интервью с партнёром (искать в Telegram-чатах по алгоритмам).

Модуль 0 · Фундамент: сложность и модель вычислений

Теория: асимптотика Big-O / Ω / Θ, амортизированный анализ, оценка по времени и памяти, классы сложности (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)).

Зачем: интервьюер ВСЕГДА просит оценить решение; неверная оценка → критика и переоценка.

Материалы

• 🎥 Сложность и модели вычислений — М. А. Бабенко (Yandex for ML) и плейлист курса (12 видео).
• 🎥 Алгоритмы и структуры данных. Введение. Массивы (VK Team).
• 📚 Stepik: Алгоритмы — теория и практика (CS Center).

Модуль 1 · Массивы, строки, два указателя

Паттерн: два указателя (встречные / попутные), in-place преобразования.

Уточняющие вопросы (всегда задавать): отсортирован ли массив; только ASCII; возможны ли дубликаты; можно ли менять in-place.

Разобранный пример — Two Sum (отсортированный массив)

func twoSum(_ nums: [Int], _ target: Int) -> (Int, Int)? {
    var l = 0, r = nums.count - 1            // O(1) память
    while l < r {                            // O(n) время
        let s = nums[l] + nums[r]
        if s == target { return (l, r) }
        else if s < target { l += 1 }
        else { r -= 1 }
    }
    return nil
}

Задачи: Two Sum / Two Sum II, Valid Palindrome, Container With Most Water, 3Sum, Remove Duplicates, Trapping Rain Water ★★★.

Модуль 2 · Sliding Window

Паттерн: окно фиксированной/переменной длины; явно упомянут как тема собесов в Яндексе.

Задачи: Permutation in String, Max Consecutive Ones III, Longest Substring Without Repeating Characters, Minimum Window Substring ★★★, Best Time to Buy and Sell Stock.

Модуль 3 · Хеш-таблицы и множества

Теория: хеш-функции, коллизии (частый теоретический вопрос), разрешение коллизий (цепочки/открытая адресация), сложность операций. В Swift: Dictionary, Set, протокол Hashable.

Задачи: Group Anagrams, Top K Frequent Elements, Subarray Sum Equals K, Longest Consecutive Sequence.

Модуль 4 · Стек, очередь, дек

Паттерн: монотонный стек, парные скобки, очередь через два стека.

Задачи: Valid Parentheses, Min Stack, Daily Temperatures, Largest Rectangle in Histogram ★★★, Sliding Window Maximum (дек).

Модуль 5 · Связные списки

Паттерн: fast/slow указатели, разворот, dummy-узел.

Задачи: Reverse Linked List, Linked List Cycle, Merge Two Sorted Lists, Reorder List, Remove Nth Node, LRU Cache ★★★ — пересекается с System Design!

Модуль 6 · Бинарный поиск

Паттерн: поиск по значению и по ответу (binary search on answer); оценить сложность O(log n).

Задачи: Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Array, Koko Eating Bananas, Median of Two Sorted Arrays ★★★.

Модуль 7 · Деревья (бинарные, BST)

Паттерн: DFS (pre/in/post), BFS по уровням, рекурсия; явно упомянуты «бинарное дерево» и Find Duplicate Subtrees.

Задачи: Invert Binary Tree, Max Depth, Diameter, Level Order Traversal, Validate BST, Lowest Common Ancestor, Find Duplicate Subtrees, Serialize/Deserialize ★★★.

Модуль 8 · Графы (BFS/DFS, топосорт, Union-Find)

Паттерн: обход матрицы/списка смежности, поиск компонент, обнаружение циклов, кратчайшие пути (BFS/Dijkstra).

Задачи: Number of Islands, Clone Graph, Course Schedule (топосорт), Pacific Atlantic Water Flow, Word Ladder, Number of Connected Components (Union-Find).

Модуль 9 · Куча / приоритетная очередь

Теория: binary heap, k-й элемент, слияние k списков. В Swift нет встроенной heap — уметь реализовать или использовать Heap из swift-collections.

Задачи: Kth Largest Element, Top K Frequent, Merge k Sorted Lists, Find Median from Data Stream ★★★, Task Scheduler.

Модуль 10 · Backtracking

Паттерн: перебор с возвратом, дерево решений, отсечения.

Задачи: Subsets, Permutations, Combination Sum, Word Search, N-Queens, Palindrome Partitioning.

Модуль 11 · Динамическое программирование

Теория: оптимальная подструктура, перекрывающиеся подзадачи, мемоизация ↔ табуляция, 1D/2D DP.

• 🎥 Dynamic Programming — freeCodeCamp (5 ч, EN).

Задачи: Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, Longest Common Subsequence, Edit Distance, 0/1 Knapsack, Unique Paths, Word Break.

Модуль 12 · Жадные алгоритмы и интервалы

Паттерн: сортировка + жадный выбор, слияние интервалов.

Задачи: Merge Intervals, Insert Interval, Non-overlapping Intervals, Jump Game, Gas Station, Meeting Rooms II.

Протокол ответа на алго-интервью

Распечатать и отрепетировать:

1. Прочитать условие внимательно.
2. Задать уточняющие вопросы (сортировка, дубликаты, диапазон, ASCII, in-place?).
3. Проговорить алгоритм словами — думать вслух.
4. Привести тест-кейсы, оценить время/память (Big-O).
5. Сообщить о готовности → писать код.
6. Перечитать, исправить синтаксис/логику, мысленный дебаг, граничные случаи.
7. Сдать и проговорить итог.

Дневник ошибок (шаблон)

Недельный план (8 недель)

Темп ~2 задачи/день, до 30 мин на задачу, интервальное повторение слабых тем.

Критерии готовности

0 из 4 · 0%