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.