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

Вопросы про структуры данных проверяют, умеете ли вы сопоставить паттерны доступа с нужной абстракцией. Массивы сильны в индексированном доступе и последовательном обходе. Связные списки жертвуют индексацией ради дешёвой перестановки указателей. Стеки и очереди кодируют инварианты LIFO и FIFO. Hash map покупает средний O(1) lookup ценой памяти. Деревья и графы моделируют иерархию и связи; heap — выбор по приоритету.

Перед кодом спросите: какие операции доминируют — lookup, insert, delete, min/max, prefix search или traversal? Ответ определяет выбор структуры сильнее, чем привычка к одному паттерну.

На интервью: называйте среднюю и худшую сложность, сравнивайте минимум два варианта и объясняйте компромисс по памяти.

Типовые ошибки: hash map, когда нужен sorted order; Array.shift как очередь в чувствительном к производительности коде; предположение о сбалансированном дереве при перекошенном входе.

Чеклист:

• Перечислите доминирующие операции.
• Сравните время, память и гарантии порядка.
• Углубляйтесь через дочерние темы.
• Проверьте пустой, одноэлементный и патологический вход.