Como você projeta uma estrutura de dados com requisitos específicos de O(1)/O(log n)?

Question

Accepted Answer

Projetar uma estrutura customizada significa **compor estruturas existentes** de forma que cada operação necessária atinja sua complexidade alvo, permitindo que uma estrutura cubra a fraqueza de outra. A técnica clássica é emparelhar um **hash map** com um **array, heap ou lista ligada**.

## Um exemplo prático: insert, delete, getRandom — todos O(1)

Requisitos: `insert(x)`, `remove(x)` e `getRandom()` cada um em O(1). Um hash map sozinho não consegue O(1) aleatório; um array sozinho não consegue O(1) remoção. **Combine-os**.

```python
import random
class RandomizedSet:
    def __init__(self):
        self.idx = {}      # value -> index in list
        self.vals = []     # values for O(1) random pick
    def insert(self, x):                    # O(1)
        if x in self.idx: return False
        self.idx[x] = len(self.vals)
        self.vals.append(x)
        return True
    def remove(self, x):                    # O(1): swap with last, pop
        if x not in self.idx: return False
        i, last = self.idx[x], self.vals[-1]
        self.vals[i] = last                 # move last into the hole
        self.idx[last] = i
        self.vals.pop()
        del self.idx[x]
        return True
    def getRandom(self):                    # O(1)
        return random.choice(self.vals)
```

## Uma receita geral de design

```text
1. List every required operation + its target complexity.
2. For each, name a structure that hits it:
     by key O(1)      -> hash map
     by index O(1)    -> array
     min/max O(log n) -> heap
     ordered O(log n) -> balanced tree / skip list
     O(1) splice      -> doubly linked list
3. COMBINE them; use the hash map to map keys -> positions/nodes
   in the other structure so updates stay O(1).
4. Verify each operation against its target.
```

| Padrão | Estruturas combinadas | Permite |
|---|---|---|
| Cache LRU | hash map + lista duplamente ligada | O(1) get/put |
| Conjunto randomizado O(1) | hash map + array | O(1) insert/remove/random |
| Min em O(1) em uma stack | stack + stack auxiliar de mín | O(1) getMin |

## Por que isso importa

Sistemas reais raramente precisam de uma única estrutura de livro didático — eles precisam de uma composição ajustada a um padrão de acesso específico, que é exatamente o que esses designs entregam.

Entrevistadores usam esses problemas para testar se você consegue raciocinar a partir de **custos de operação para uma composição**, a habilidade central por trás do design de sistemas de alto desempenho.

Padrão	Estruturas combinadas	Permite
Cache LRU	hash map + lista duplamente ligada	O(1) get/put
Conjunto randomizado O(1)	hash map + array	O(1) insert/remove/random
Min em O(1) em uma stack	stack + stack auxiliar de mín	O(1) getMin