Learning data structures and algorithms

Данный материал посвящён самостоятельной реализации ключевых алгоритмов и структур данных на языке Go. Цель — не только отработать практические навыки программирования, но и глубоко понять внутреннюю механику алгоритмов, что критически важно как для профессиональной работы, так и для успешного прохождения технических собеседований.

Важные оговорки

Уровень кода: намеренно упрощён для максимальной наглядности. Акцент сделан на ясность логики, а не на оптимизацию или «красивый» код.

Язык реализации: Go (Golang). Выбор обусловлен его простотой, строгой типизацией и популярностью в современной разработке.

Фокус: понимание принципов, а не готовых библиотек. Мы реализуем всё «с нуля», чтобы увидеть, как работают базовые механизмы.

Содержание

Алгоритмы сортировки

• Пузырьковая сортировка (O(n^2)) — простейший пример, иллюстрирующий идею попарного сравнения.
• Сортировка вставками (O(n^2)) — эффективна для малых массивов или почти отсортированных данных.
• Сортировка слиянием (O(nlogn)) — пример «разделяй и властвуй», стабильная и предсказуемая по времени.
Дополнение:
• Быстрая сортировка (O(nlogn) в среднем) — популярный алгоритм с рекурсивным разбиением.
• Пирамидальная сортировка (O(nlogn)) — использует структуру данных «двоичная куча».

Поиск и обход графов

• Поиск в ширину (BFS) — находит кратчайший путь в невзвешенном графе.
• Поиск в глубину (DFS) — исследует все ветви до конца, полезен для топологической сортировки.
Дополнение:
• Алгоритм Дейкстры (O((V+E)logV)) — поиск кратчайшего пути в взвешенном графе с неотрицательными рёбрами.
• Алгоритм A* — эвристический поиск с оценкой стоимости пути (применяется в играх и навигации).

Математические алгоритмы

• Числа Фибоначчи — реализация через рекурсию, итерацию и мемоизацию.
• Вычисление факториала — пример рекурсивного и итеративного подходов.
• Конечный автомат (FSM) — моделирование состояний и переходов (например, для парсинга строк).
Дополнение:
• Быстрое возведение в степень (O(logn)) — метод «возведения в квадрат».
• Алгоритм Евклида — нахождение НОД двух чисел.
• Решето Эратосфена — поиск простых чисел до заданного предела.

Структуры данных

• Стек (LIFO) — реализация на массиве или связном списке.
• Очередь (FIFO) — циклическая очередь и двусвязная реализация.
• Связные списки — односвязные и двусвязные, операции вставки/удаления.
• Деревья — бинарные деревья поиска, обходы (in-order, pre-order, post-order).
• Хэш-таблица — коллизии, методы разрешения (цепочки, открытая адресация).
Дополнение:
• Очередь с приоритетом — на основе кучи.
• AVL-дерево — самобалансирующееся двоичное дерево.
• Префиксное дерево (Trie) — для хранения и поиска строк.

Хэш-функции и основы криптографии

• Простые хэш-функции — полиномиальный хэш, CRC.
• Криптографические хэш-функции — SHA-256 (обзор принципа работы).
• Применение в структурах данных — хэш-таблицы, деревья Меркла.
Дополнение:
• HMAC — код аутентификации сообщений.
• Основы симметричного шифрования — AES (концептуально).

Дополнительные алгоритмы

Динамическое программирование — задачи «о рюкзаке», «о количестве путей».

Жадные алгоритмы — задача о размене монет, интервальное планирование.

Поиск подстроки — алгоритм Кнута-Морриса-Пратта (KMP).

Работа с большими числами — длинная арифметика (сложение, умножение).