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

Big O, деревья, графы и всё, что спрашивают на собеседованиях. Реализации на Go, идеи переносятся на любой язык

Уровень: Средний · около 4 ч · после курса: Оценишь сложность по Big O и реализуешь хеш-таблицу, дерево и обход графа руками

Чему научишься

  • Оценивать сложность алгоритма по Big O
  • Понимать, как устроены динамический массив и хеш-таблица изнутри
  • Реализовать стек, очередь и связный список
  • Работать с бинарным деревом поиска
  • Обходить графы через BFS и DFS, делать топологическую сортировку
  • Реализовать сортировку и бинарный поиск и понимать их цену

Уроки курса (8)

Модуль 1 · Сложность и внутренности

Big O, слайсы и map изнутри

  1. Big O: оцениваем скорость алгоритмов - Нотация Big O, временная и пространственная сложность, как оценивать код на глаз
  2. Динамический массив изнутри: память, capacity и подводные камни - Как устроен динамический массив на уровне памяти: разбор на слайсах Go, с переносом на list и array
  3. Хеш-таблица изнутри: коллизии, бакеты и цена O(1) - Как устроена хеш-таблица: разбор на map в Go, с переносом на dict и array

Модуль 2 · Линейные структуры и деревья

Стек, очередь, связный список, бинарное дерево

  1. Стек и очередь: два базовых контейнера - Реализация стека и очереди на слайсах, проверка скобок, BFS
  2. Связный список: когда слайс не подходит - Односвязный и двусвязный списки, container/list, сравнение со слайсами
  3. Бинарное дерево поиска - BST: вставка, поиск, удаление, обходы дерева и балансировка

Модуль 3 · Графы и сортировки

BFS/DFS, топологическая сортировка и бинарный поиск

  1. Графы: BFS, DFS и топологическая сортировка - Представление графов, обход в ширину и глубину, поиск кратчайшего пути, порядок зависимостей
  2. Сортировка и бинарный поиск - sort.Slice, sort.Interface, бинарный поиск, сравнение алгоритмов сортировки