Cum alegi structura de date corectă pentru o problemă?

Question

Accepted Answer

Alege structura ale cărei **operații cel mai frecvente sunt cel mai ieftine** pentru modelul tău de acces. Începe prin a lista operațiile pe care le vei efectua, estimează frecvența lor, apoi potrivește-le cu punctele forte ale structurii.

## Lista de verificare a deciziilor

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

## Potrivește operațiile la complexitate

| Necesitate | Cea mai bună structură | Cost operației-cheie |
|---|---|---|
| Acces aleatoriu după index | dynamic array | O(1) |
| Căutare după cheie | hash map | O(1) avg |
| Sortat + interogări de interval | balanced BST | O(log n) |
| Min/max în mod repetat | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Căutare cu prefix | trie | O(L) |

## Exemplu de raționament

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

## De ce este important

A alege bine este adesea diferența dintre o soluție O(n) și una O(n²) — cea mai mare pârghie asupra performanței.

Intervievatorii testează exact acest raționament: doresc să te vadă mapând cerințele la costurile operației, nu memorând structuri.

Necesitate	Cea mai bună structură	Cost operației-cheie
Acces aleatoriu după index	dynamic array	O(1)
Căutare după cheie	hash map	O(1) avg
Sortat + interogări de interval	balanced BST	O(log n)
Min/max în mod repetat	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Căutare cu prefix	trie	O(L)