Miten valitset oikean tietorakenteen ongelmaan?

Question

Accepted Answer

Valitse rakenne, jonka **yleisimmät operaatiot ovat halvaimpia** käyttömalliasi varten. Aloita listaamalla operaatiot, joita suoritat, arvioi niiden frekvenssi ja yhdistä ne rakenteen vahvuuksiin.

## Päätöstarkistusluettelo

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

## Yhdistä operaatiot monimutkaisuuteen

| Tarve | Paras rakenne | Avainoperaation kustannus |
|---|---|---|
| Satunnainen pääsy indeksin mukaan | dynamic array | O(1) |
| Haku avaimen mukaan | hash map | O(1) avg |
| Järjestetty + aluekyselmykset | balanced BST | O(log n) |
| Min/max toistuvasti | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Etuliitehaku | trie | O(L) |

## Esimerkki päättelystä

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

## Miksi se on tärkeää

Oikea valinta on usein ero O(n)- ja O(n²)-ratkaisun välillä — suurin vipuvarsi suorituskyvyssä.

Haastattelija testaa juuri tätä päättelyä: he haluavat nähdä, miten kartoitat vaatimukset operaatioiden kustannuksiin, eivät vain muista rakenteita.

Tarve	Paras rakenne	Avainoperaation kustannus
Satunnainen pääsy indeksin mukaan	dynamic array	O(1)
Haku avaimen mukaan	hash map	O(1) avg
Järjestetty + aluekyselmykset	balanced BST	O(log n)
Min/max toistuvasti	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Etuliitehaku	trie	O(L)