Comment concevoir une structure de données avec des exigences spécifiques O(1)/O(log n) ?

Question

Accepted Answer

Concevoir une structure personnalisée signifie **composer des structures existantes** de sorte que chaque opération requise atteigne sa complexité cible, en laissant une structure couvrir la faiblesse d'une autre. La technique classique est d'associer une **table de hachage** avec un **tableau, un tas ou une liste chaînée**.

## Un exemple concret : insert, delete, getRandom — tous O(1)

Exigences : `insert(x)`, `remove(x)` et `getRandom()` chacun en O(1). Une table de hachage seule ne peut pas faire O(1) aléatoire ; un tableau seul ne peut pas faire O(1) remove. **Combinez-les**.

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

## Une recette de conception générale

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

| Motif | Structures combinées | Permet |
|---|---|---|
| Cache LRU | table de hachage + liste doublement chaînée | O(1) get/put |
| Ensemble aléatoire O(1) | table de hachage + tableau | O(1) insert/remove/random |
| Min en O(1) sur une pile | pile + pile auxiliaire min | O(1) getMin |

## Pourquoi c'est important

Les systèmes réels nécessitent rarement une seule structure de manuel — ils ont besoin d'une composition accordée à un modèle d'accès spécifique, ce qui est exactement ce que ces designs livrent.

Les enquêteurs utilisent ces problèmes pour tester si vous pouvez raisonner à partir des **coûts d'opération à une composition**, la compétence essentielle derrière la conception de systèmes haute performance.

Motif	Structures combinées	Permet
Cache LRU	table de hachage + liste doublement chaînée	O(1) get/put
Ensemble aléatoire O(1)	table de hachage + tableau	O(1) insert/remove/random
Min en O(1) sur une pile	pile + pile auxiliaire min	O(1) getMin