Jak zaprojektować strukturę danych z konkretnymi wymaganiami O(1)/O(log n)?

Question

Accepted Answer

Projektowanie struktury niestandardowej oznacza **komponowanie istniejących struktur** w taki sposób, aby każda wymagana operacja osiągnęła docelową złożoność, pozwalając jednej strukturze pokryć słabości innej. Klasyczną techniką jest połączenie **mapy haszowej** z **tablicą, kopcem lub listą powiązaną**.

## Praktyczny przykład: insert, delete, getRandom — wszystko O(1)

Wymagania: `insert(x)`, `remove(x)` i `getRandom()` każde w O(1). Sama mapa haszowa nie może osiągnąć O(1) dla losowego dostępu; sama tablica nie może osiągnąć O(1) dla usunięcia. **Połącz je**.

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

## Ogólny przepis projektowania

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

| Wzorzec | Połączone struktury | Umożliwia |
|---|---|---|
| Pamięć podręczna LRU | mapa haszowa + lista powiązana z dwoma kierunkami | O(1) get/put |
| Zbiór z losowaniem O(1) | mapa haszowa + tablica | O(1) insert/remove/random |
| Min w O(1) na stosie | stos + pomocniczy stos minimów | O(1) getMin |

## Dlaczego to ważne

Systemy rzeczywiste rzadko potrzebują pojedynczej struktury z podręcznika — potrzebują kompozycji dostrojonej do konkretnego wzorca dostępu, co jest dokładnie tym, co te projekty dostarczają.

Rozmówcy używają tych problemów, aby sprawdzić, czy potrafisz rozumować od **kosztów operacji do kompozycji**, co jest kluczową umiejętnością za projektowaniem systemów o wysokiej wydajności.

Wzorzec	Połączone struktury	Umożliwia
Pamięć podręczna LRU	mapa haszowa + lista powiązana z dwoma kierunkami	O(1) get/put
Zbiór z losowaniem O(1)	mapa haszowa + tablica	O(1) insert/remove/random
Min w O(1) na stosie	stos + pomocniczy stos minimów	O(1) getMin