Структуры данных
Структуры данных на Python-собеседовании спрашивают не по учебнику алгоритмов, а по стандартной библиотеке. Вопрос звучит как «что такое очередь», но интервьюер ждёт продолжения — на чём вы её построите и во что это обойдётся. В CPython у каждой абстракции есть конкретный носитель, и он же задаёт сложность: стек живёт на list, очередь — на collections.deque, куча — на плоском list через heapq, граф — на dict списков смежности. А сбалансированного дерева поиска в стандартной библиотеке нет вообще, и это надо уметь сказать вслух вместе с тем, чем его заменяют.
Отсюда три ловушки, которые встречаются чаще остальных. list.pop(0) выглядит как извлечение из очереди, но стоит O(n) — все оставшиеся указатели сдвигаются влево одним memmove, и обход графа тихо становится квадратичным. heapq реализует только min-heap, поэтому максимум достают отрицанием ключа, а кортеж-приоритет (priority, item) падает с TypeError ровно тогда, когда два приоритета совпали, а сами элементы несравнимы. Матрица смежности в чистом Python — это не V² бит, а V² указателей по восемь байт. Каждый слой ниже разбирает свой носитель вместе с его настоящей ценой.
Карта темы
- Стек и очередь — LIFO против FIFO, почему
listидеален для стека и провален для очереди, и что даётcollections.deque. - Деревья — связный ацикличный граф из
nузлов иn-1рёбер, обходы вглубь и вширь, лимит рекурсии CPython. - Двоичное дерево поиска — инвариант порядка на всё поддерево, вырождение в цепочку на отсортированном входе и чем заменить отсутствующий в stdlib балансирующий BST.
- Куча и heapq — частичный порядок на плоском списке,
heapifyзаO(n), отрицание для max-heap и кортежные приоритеты со счётчиком. - Графы — направленность, веса, циклы, обязательное множество
visitedи обходы заO(V+E). - Представление графа в памяти — список против матрицы смежности,
O(V+E)противO(V²)и когда матрица всё-таки выигрывает.
Частые ошибки и ловушки
| Ошибка | Последствие |
|---|---|
Строить очередь на list и извлекать через pop(0) | Каждое извлечение сдвигает весь хвост — O(n) вместо O(1), и обход графа становится квадратичным |
Считать, что heapq умеет max-heap | Модуль реализует только min-heap; максимум получают отрицанием ключа или обёрткой с инвертированным __lt__ |
Класть в кучу (priority, item) с несравнимыми элементами | При равных приоритетах сравнение проваливается на второй элемент кортежа и падает с TypeError |
| Проверять инвариант BST только у прямых потомков | Валидатор пропустит дерево, где внук нарушает границу деда; проверять надо коридор (low, high) |
Утверждать, что поиск в BST всегда O(log n) | Без балансировки отсортированный вход вырождает дерево в цепочку и даёт O(n) |
| Искать в стандартной библиотеке готовый сбалансированный BST | Его там нет — берут dict, bisect над отсортированным списком или сторонний sortedcontainers |
Обходить граф без множества visited | Первый же цикл делает обход бесконечным, а на ромбовидном DAG даёт экспоненциальное число повторных заходов |
| Брать матрицу смежности для разреженного графа | O(V²) ссылок вместо O(V+E) — сотни мегабайт там, где хватило бы единиц |
| Путать кучу с деревом поиска | Куча упорядочена только по вертикали, родитель ≤ потомков; печать её списка не даёт отсортированной последовательности |
Значение для собеседований
Формулировки вопросов обманчиво простые — «чем стек отличается от очереди», «что такое дерево», «что такое граф». Первую половину ответа знает каждый, и она интервьюеру неинтересна; вся оценка происходит во второй половине, где вы называете носитель и сложность. Ответ «очередь — это FIFO» закрывает вопрос на джуна; ответ «очередь — это FIFO, и в Python её строят на collections.deque, потому что у list извлечение из головы стоит O(n)» закрывает его на мидла. Ровно так же с кучей: «полное двоичное дерево» — половина, а вторая половина — «модуль heapq поверх обычного списка, только min-heap, heappush/heappop за O(log n), heapify за O(n)».
Дальше идут два уточняющих хода, на которых сыплются чаще всего. Первый — вопрос про худший случай: «а если ключи вставлять по возрастанию?» Правильный ответ отделяет сбалансированное дерево от несбалансированного и честно называет O(n). Второй — вопрос про выбор представления: «граф на десять тысяч вершин и двадцать тысяч рёбер, что возьмёте?» Здесь ждут не названия, а арифметики — список смежности даёт порядок V+E ячеек, матрица V², разница в тысячи раз. Типичная ошибка на обоих вопросах одинаковая — кандидат уверенно повторяет определение из учебника и ни разу не произносит букву O. Если тема идёт глубже, спрашивают про реализацию очереди на двух стеках, про то, почему heapify линеен, а не O(n log n), и про то, чем вы замените отсутствующий в стандартной библиотеке TreeMap.