Как выбрать правильную структуру данных для задачи?

Question

Accepted Answer

Выберите структуру, в которой **самые частые операции самые дешевые** для вашего паттерна доступа. Начните со списка операций, которые вы будете выполнять, оцените их частоту, а затем сопоставьте их с сильными сторонами структуры.

## Контрольный список решений

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Сопоставьте операции со сложностью

| Необходимо | Лучшая структура | Стоимость ключевой операции |
|---|---|---|
| Случайный доступ по индексу | dynamic array | O(1) |
| Поиск по ключу | hash map | O(1) avg |
| Отсортировано + запросы диапазона | balanced BST | O(log n) |
| Мин/макс повторно | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Поиск префикса | trie | O(L) |

## Пример рассуждений

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Почему это важно

Правильный выбор часто — это разница между решением O(n) и O(n²) — самый большой рычаг влияния на производительность.

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

Необходимо	Лучшая структура	Стоимость ключевой операции
Случайный доступ по индексу	dynamic array	O(1)
Поиск по ключу	hash map	O(1) avg
Отсортировано + запросы диапазона	balanced BST	O(log n)
Мин/макс повторно	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Поиск префикса	trie	O(L)