Data Structures and Algorithms Notebook

Реализация популярных структур данных и алгоритмов на Python с акцентом на практические задачи и собеседования.

---

Описание

• Представлены 80+ задач на 15+ тем из разных областей алгоритмов
• Широкий охват тем: от базовых алгоритмов и структур данных до продвинутых методов и теории чисел
• Задачи из реальных собеседований, LeetCode, Stepik, тренировок от Яндекса и других источников
• Прокомментированные решения на Python (иногда даже несколько вариантов)
• Теоретические Markdown конспекты, объясняющие ключевые идеи и подходы к решению задач
• 1000+ автоматизированных тестов (pytest) для проверки корректности
• Качество кода гарантировано Ruff и Mypy (автоматическая проверка после коммита)

Охваченные темы

Темы расположены в порядке увеличения сложности, начиная с базовых алгоритмов и заканчивая продвинутыми структурами данных и алгоритмами.

№	Кодовое имя	Тема	Секция	Описание
1	intro	Введение в алгоритмы	Введение в алгоритмы	Введение в алгоритмы, базовые задачи и методы решения. Числа Фибоначчи. Линейный поиск. Нахождение 1, 2, 3 максимумов в массиве.
2	base_ds	Базовые структуры данных	Введение в алгоритмы	Использование массивов, стеков, очередей и двухсторонних очередей (деков) для решения задач. Основные операции и алгоритмы на этих структурах.
3	search	Поиски	Введение в алгоритмы	Поиски на отсортированных данных: бинарный, удваивающися и экспоненциальный. Их применение и оптимизации.
4	sorting	Сортировки	Введение в алгоритмы	Классические алгоритмы сортировки: сортировка вставками, выбором, пузырьком, слиянием и быстрая сортировка. Сортировка подсчетом, поразрядная сортировка.
5	two_pointers	Два указателя	Методы решения	Методы решения задач на массивы и строки с помощью двух указателей. Поиск пар чисел и анализ подстрок
6	scanline	Сканирующая прямая	Методы решения	Решение задач на отрезках и интервалах с помощью сканирующей прямой. Нахождение пересечений, объединений и покрытий.
7	dnc	Разделяй и властвуй	Методы решения	Разбиение на независимые подзадачи. Быстрое возведение в степень, поиск медианы и k-й порядковой статистики. Алгоритм Карацубы
8	dp	Динамическое программирование	Методы решения	Разбиение на пересекающиеся подзадачи. Классические задачи: рюкзак, размен монет, наибольшая возрастающая подпоследовательность. Восстановленеи пути.
9	prefix_sums	Префиксные суммы	Продвинутые методы	Использование префиксных сумм для оптимизации запросов на отрезках. Решение задач на суммы, произведения и другие агрегаты.
10	greedy	Жадные алгоритмы	Продвинутые методы	Жадные алгоритмы для оптимальных решений. Задачи на выбор оптимальных элементов, планирование задач и нахождение минимальных покрытий.
11	number_theory	Теория чисел	Продвинутые методы	Теоретические задачи на делимость, простые числа, алгоритмы Евклида и расширенного Евклида, факторизацию и тесты на простоту.
12	dp2	2D Динамическое программирование	Продвинутые методы	Применение ДП на двухмерных даннных. Классические задачи: расстояние редактирования, наибольшая общая подпоследовательность, денежный робот.
13	trees	Деревья	Продвинутые структуры данных	Двоичные деревья поиска. Алгоритмы обхода DFS и BFS. Поиск высоты дерева и проверка общих свойств BST. Итеративные и рекурсивные алгоритмы.
14	heaps	Кучи	Продвинутые структуры данных	Реализация кучи (очереди с приоритетом) на массиве. Алгоритмы вставки, удаления и извлечения максимума. Сортировка кучей. Алгоритм Хаффмана.
15	dsu	Непересекающиеся множества	Продвинутые структуры данных	Реализация структуры данных "Непересекающиеся множества" (DSU/Union-Find). Алгоритмы объединения и поиска. Применение в задачах на компоненты связности.
16	hash_tables	Хеш-таблицы	Продвинутые структуры данных	Реализация хеш-таблицы на массиве. Алгоритмы вставки, удаления и поиска. Разрешение коллизий с помощью цепочек и открытой адресации.
17	graphs	Графы	Продвинутые структуры данных	Реализация графов с помощью списков смежности. Алгоритмы обхода DFS и BFS. Нахождение кратчайших путей (Dijkstra, Bellman-Ford).

---

Файловая структура

• src - папка с условиями и решениями задач по темам
• tests - папка с автотестами для каждого решения
• abstract - папка с теоретическими конспектами по каждой теме
• assets - дополнительные материалы, такие как презентации, схемы и диаграммы

Например, для темы "Введение в алгоритмы" структура будет следующей:

src/
├── intro
│   ├── README.md          # Подборка задач
│   ├── fib.py             # Решение задачи на Fibonacci
│   └── ...
tests/
├── test_intro
│   ├── test_fib.py        # Автотесты для решения на Fibonacci
│   └── ...
abstract/
├── intro.md               # Теоретический конспект по теме "Введение в алгоритмы"
├── base_ds.md             # Теоретический конспект по теме "Базовые структуры данных"
└── ...

---

Локальное использование

1. Склонируйте репозиторий:

   git clone https://github.com/everysoftware/algorithms-course

2. Создайте виртуальное окружение:

   python -m venv venv
   source venv/bin/activate  # Linux/MacOS
   venv\Scripts\activate     # Windows

3. Установите зависимости:

   pip install -r requirements.txt

4. Запустите нужные тесты, например, для задачи "Числа Фибоначчи":

    pytest tests/test_intro/test_fib.py

5. Изучайте теорию в папке abstract и решайте задачи в папке src. Не забывайте запускать тесты для проверки своих решений!

---

Made with ❤️