re:re:actable
Урок 006 минут чтения

Карта раздела для новичка

На этой странице
Кратко

Начинать стоит не с сортировок, а с того, как читать задачу и проверять решение руками. Дальше - Big O, базовые структуры данных, поиск и сортировка, паттерны, деревья и графы, рекурсия и DP. Этот урок - маршрут по разделу и словарь английских терминов, которые встречаются в каждом уроке.

Вопрос

С чего начать изучение алгоритмов и в каком порядке проходить раздел?

Как устроен раздел

Уроки разделов 01-08 короткие: в них главная идея, код, сложность и ответ для собеседования. Раздел 09 написан подробнее, специально для новичка: в нем процесс решения задач и темы, которые в основной части не поместились.

Если вы только начинаете, идите по маршруту ниже, а не по номерам папок.

Маршрут

Шаг 1. Как вообще решать задачи

  1. Как новичку читать алгоритмическую задачу
  2. Как делать dry run - ручная трассировка понадобится в каждом следующем уроке.

Шаг 2. Сложность

  1. Что такое алгоритм
  2. Big O notation, затем остальные уроки темы База и сложность алгоритмов.

Шаг 3. Инструменты JavaScript и линейные структуры

  1. Array, Map, Set.
  2. Тема Линейные структуры данных: array, linked list, stack, queue, hash table, heap.
  3. Как выбирать структуру данных под задачу - связывает все предыдущее.

Уроки про TypeScript и generics можно отложить: они полезны, но не обязательны для понимания алгоритмов.

Шаг 4. Поиск и сортировка

  1. Тема Поиск и сортировка по порядку.
  2. Как избегать off by one - сразу после binary search.

Шаг 5. Паттерны

  1. Как превращать brute force в оптимальное решение - объясняет, зачем паттерны вообще нужны.
  2. Тема Паттерны решения задач: two pointers, sliding window, prefix sums, hash map, intervals, monotonic stack, fast/slow pointers, backtracking.
  3. Как доказывать корректность через инварианты.

Шаг 6. Деревья, графы, рекурсия и DP

  1. Как работает рекурсия - ее лучше понять до деревьев.
  2. Тема Деревья и графы, затем Matrix и grid.
  3. Остальная тема Рекурсия, DP и greedy.

Шаг 7. Дополнительные темы

  1. Trie, Union Find, bit manipulation, математика, продвинутые графы.

Шаг 8. Подготовка к собеседованию

  1. Тема Практика и собеседования: процесс решения, разговор о сложности, список задач и план подготовки.

Как проходить урок

  1. Прочитайте идею и код.
  2. Повторите трассировку из урока на бумаге, не подглядывая.
  3. Перепишите код сами в песочнице и запустите на своих примерах, включая пустой input.
  4. Решите 1-2 задачи на этот паттерн (список - в уроке Какие задачи нужно уметь решать).
  5. Через несколько дней вернитесь к карточке урока и ответьте на вопрос вслух.

Словарь терминов

В уроках много английских слов: так говорят на собеседованиях и так называются задачи на LeetCode. Основные:

ТерминЧто значит
input / outputвходные данные / результат функции
constraintsограничения из условия: размер n, диапазон чисел
edge caseкрайний случай: пустой массив, один элемент, отрицательные числа
happy path"обычный" вход, на котором все работает
brute forceрешение "в лоб", перебором
baselineпростое правильное решение, с которым сравнивают оптимизацию
dry run, traceручной прогон алгоритма по шагам
time / space complexityсколько времени / дополнительной памяти нужно в зависимости от n
auxiliary spaceдополнительная память без учета input и output
amortized"в среднем на операцию" с учетом редких дорогих операций
best / average / worst caseлучший / средний / худший вариант входных данных
in-placeалгоритм меняет исходный массив и почти не берет память
mutateизменять исходные данные
stable sortсортировка, сохраняющая порядок равных элементов
comparatorфункция сравнения (a, b) => number для sort
pivotопорный элемент в quick sort
pointerиндекс или ссылка, которую двигают по данным
windowнепрерывный кусок массива [left, right]
prefixначало массива или строки
contiguousидущий подряд, без пропусков
subarray / substringнепрерывный кусок массива / строки
subsequenceэлементы в том же порядке, но не обязательно подряд
node, vertexузел, вершина
edgeребро, связь между вершинами
root / leafкорень / лист (узел без детей) дерева
visitedмножество уже посещенных вершин
adjacency listсписок соседей для каждой вершины
directed / weightedориентированный граф / граф с весами на ребрах
DAGориентированный граф без циклов
base caseслучай, когда рекурсия останавливается
memoizationкеш ответов уже решенных подзадач
DP, state, transitionдинамическое программирование; что хранит ячейка; как она считается
greedyжадный алгоритм: берет лучший вариант прямо сейчас
invariantутверждение, которое верно на каждом шаге алгоритма
pruningотсечение веток перебора, которые точно не дадут ответ
trade-offкомпромисс: например, больше памяти ради скорости
off-by-oneошибка на единицу в индексах или границах

Что отвечать на собеседовании?

Если спрашивают, как готовиться к алгоритмам, хороший ответ такой: сначала нужно понять базовые структуры данных и Big O, затем научиться разбирать задачу: вход, выход, ограничения, примеры, edge cases. После этого решают brute force, ищут повторную работу, подбирают структуру данных или паттерн, делают dry run, доказывают корректность через инвариант и только потом пишут код.

Мини-шпаргалка

  • Начинайте с чтения задачи и dry run, а не с сортировок.
  • Каждую задачу начинайте с input/output/constraints.
  • Делайте dry run до и после кода.
  • Структура данных выбирается по операции, которую нужно ускорить.
  • Brute force - полезная стартовая точка.
  • Корректность объясняется инвариантом или свойством паттерна.
  • Незнакомый термин - смотрите словарь в этом уроке.

Документация

NeetCode Roadmap, VisuAlgo - анимации структур данных и алгоритмов.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам