Шпаргалка Python
Основы
Функции
ООП
Многопоточность, многопроцессорность и асинхронность
Алгоритмы и структуры данных
- Введение в Алгоритмы
- Что такое алгоритм?
- Определение: последовательность шагов для решения задачи
- Свойства хорошего алгоритма: вход, выход, однозначность, конечность, эффективность
- Примеры алгоритмов в повседневной жизни (рецепт, маршрут)
- Что такое структура данных?
- Определение: способ организации и хранения данных для эффективного доступа и модификации
- Зачем нужны разные структуры данных?
- Связь между алгоритмами и структурами данных: «Алгоритмы + Структуры данных = Программы» (Н. Вирт)
- Как выбирать подходящую структуру данных?
- Критерии выбора: частота операций, объем данных, требования к памяти, читаемость кода
- Пример: когда использовать list, а когда set?
- Оценка сложности алгоритмов
- Что такое Big-O, Omega и Theta нотации? (шпора www.bigocheatsheet.com)
- Временная сложность (Time Complexity) vs Пространственная сложность (Space Complexity)
- Best, Average и Worst case сценарии
- Что такое амортизированная сложность?
- Почему
list.append() имеет сложность O(1)?
- Встроенные структуры данных
- Как реализован список (
list) внутри Python?
- Как реализован словарь (
dict) и множество (set)?
- Что такое хеш-функция и как она работает в Python?
- Что происходит при коллизии хешей в словаре?
- Почему ключом словаря может быть только хешируемый объект?
- сложность операций
in для списка, множества и словаря
- сложность операций доступа, вставки и удаления для основных коллекций (алгоритмическая сложность основных операций в коллекциях)
- Модуль
collections и heapq
- Чем
deque отличается от list и когда его использовать?
- Как работает
defaultdict?
- Для чего нужен
Counter?
- Что такое
namedtuple и dataclasses?
- Как работает модуль
heapq?
- Как реализовать приоритетную очередь в Python?
- Сортировка и Поиск
- Какой алгоритм сортировки использует Python (
sorted, list.sort)?
- Что такое стабильность сортировки и важен ли она в Python?
- Как сортировать сложные объекты (по ключу, в обратном порядке)?
- Что такое модуль
bisect?
- Как реализовать бинарный поиск вручную?
- сложность поиска в отсортированном списке vs хеш-таблице
- Алгоритмические паттерны
- Паттерн «Два указателя» (Two Pointers)
- Паттерн «Скользящее окно» (Sliding Window)
- Паттерн «Префиксные суммы» (Prefix Sum)
- Использование хеш-таблиц для оптимизации поиска
- Когда стоит использовать жадные алгоритмы?
- Классические структуры данных в Python
- Как реализовать Стек (
Stack) и Очередь (Queue)?
- Почему в Python нет встроенного связного списка (
Linked List)?
- Как реализовать Дерево (
Tree) и Граф (Graph)?
- Что такое список смежности (
Adjacency List)?
- Обход графа в ширину (
BFS) и в глубину (DFS)
- Что такое рекурсивный спуск?
- Строки и работа с текстом
- Неизменяемость строк в Python и её влияние на производительность
- Почему нельзя конкатенировать строки в цикле через
+?
- Как работает
join() и почему он эффективнее?
- Поиск подстроки: оператор
in vs метод find()
- Что такое регулярные выражения и модуль
re?
Pytest