Jak wybierasz właściwą strukturę danych do problemu?

Question

Accepted Answer

Wybierz strukturę, w której **najczęstsze operacje są najtańsze** dla Twojego wzorca dostępu. Zacznij od wymienienia operacji, które wykonasz, oszacuj ich częstotliwość, a następnie dopasuj je do mocnych stron struktury.

## Dlaczego to ważne

```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)
```

## Dopasuj operacje do złożoności

| Potrzeba | Najlepsza struktura | Koszt klucza operacyjnego |
|---|---|---|
| Dostęp losowy według indeksu | dynamic array | O(1) |
| Wyszukiwanie po kluczu | hash map | O(1) avg |
| Posortowane + zapytania zakresu | balanced BST | O(log n) |
| Min/max wielokrotnie | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Wyszukiwanie prefiksu | trie | O(L) |

## Przykładowe rozumowanie

```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)
```

## Dlaczego to ważne

Wybór właściwie to często różnica między rozwiązaniem O(n) a O(n²) — największa pojedyncza dźwignia na wydajność.

Rozmówcy testują dokładnie takie rozumowanie: chcą zobaczyć, jak mapujesz wymagania na koszty operacyjne, nie zapamiętywanie struktur.

Potrzeba	Najlepsza struktura	Koszt klucza operacyjnego
Dostęp losowy według indeksu	dynamic array	O(1)
Wyszukiwanie po kluczu	hash map	O(1) avg
Posortowane + zapytania zakresu	balanced BST	O(log n)
Min/max wielokrotnie	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Wyszukiwanie prefiksu	trie	O(L)