Como você escolhe a estrutura de dados certa para um problema?

Question

IT Interview Practice · Accepted Answer

Escolha a estrutura cujas **operações mais frequentes sejam mais baratas** para seu padrão de acesso. Comece listando as operações que você executará, estime sua frequência e depois as corresponda aos pontos fortes da estrutura.

## Lista de verificação de decisão

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

## Corresponder operações à complexidade

| Necessidade | Melhor estrutura | Custo da operação-chave |
|---|---|---|
| Acesso aleatório por índice | dynamic array | O(1) |
| Busca por chave | hash map | O(1) avg |
| Ordenado + consultas de intervalo | balanced BST | O(log n) |
| Mín/máx repetidamente | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Busca de prefixo | trie | O(L) |

## Exemplo de raciocínio

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

## Por que isso importa

Escolher bem é frequentemente a diferença entre uma solução O(n) e uma O(n²) — a maior alavanca única no desempenho.

Os entrevistadores testam exatamente esse raciocínio: eles querem ver você mapear requisitos para custos operacionais, não memorizar estruturas.

Necessidade	Melhor estrutura	Custo da operação-chave
Acesso aleatório por índice	dynamic array	O(1)
Busca por chave	hash map	O(1) avg
Ordenado + consultas de intervalo	balanced BST	O(log n)
Mín/máx repetidamente	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Busca de prefixo	trie	O(L)

Lista de verificação de decisão

Corresponder operações à complexidade

Exemplo de raciocínio

Por que isso importa

Perguntas relacionadas