Wie entwerfen Sie eine Datenstruktur mit spezifischen O(1)/O(log n)-Anforderungen?

Question

Accepted Answer

Das Entwerfen einer benutzerdefinierten Struktur bedeutet **das Kombinieren vorhandener Strukturen**, so dass jede erforderliche Operation ihre Zielkomplexität erreicht, wodurch eine Struktur die Schwäche einer anderen ausgleicht. Die klassische Technik ist das Paaren einer **Hash Map** mit einem **Array, Heap oder verketteten Liste**.

## Ein praktisches Beispiel: insert, delete, getRandom — alle O(1)

Anforderungen: `insert(x)`, `remove(x)` und `getRandom()` jeweils in O(1). Eine Hash Map allein kann kein O(1) Zufallselement liefern; ein Array allein kann kein O(1) Löschen. **Kombinieren Sie sie**.

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

## Warum es wichtig ist

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

| Muster | Kombinierte Strukturen | Ermöglicht |
|---|---|---|
| LRU cache | Hash Map + doppelt verkettete Liste | O(1) get/put |
| O(1) randomisierte Menge | Hash Map + Array | O(1) insert/remove/random |
| Min in O(1) auf einem Stack | Stack + Hilfs-Min-Stack | O(1) getMin |

## Warum es wichtig ist

Echte Systeme benötigen selten eine einzelne Standard-Struktur — sie benötigen eine Komposition, die auf ein spezifisches Zugriffsmuster abgestimmt ist, was genau das ist, was diese Designs liefern.

Interviewer verwenden diese Probleme, um zu testen, ob Sie von **Operationskosten zu einer Komposition** schlussfolgern können, die Kernfähigkeit hinter hochperformanten Systementwerfen.

Muster	Kombinierte Strukturen	Ermöglicht
LRU cache	Hash Map + doppelt verkettete Liste	O(1) get/put
O(1) randomisierte Menge	Hash Map + Array	O(1) insert/remove/random
Min in O(1) auf einem Stack	Stack + Hilfs-Min-Stack	O(1) getMin