Hvordan designer du en datastruktur med specifikke O(1)/O(log n)-krav?

Question

Accepted Answer

Design af en tilpasset struktur betyder at kombinere eksisterende strukturer så hver påkrævet operation rammer sin målkompleksitet, hvilket gør det muligt for én struktur at dække en andens svaghed. Den klassiske teknik er at sammenkæde et hash map med et array, heap eller linked list.

Et praktisk eksempel: insert, delete, getRandom — alle O(1)

Krav: , og hver i O(1). Et hash map alene kan ikke gøre O(1) random; et array alene kan ikke gøre O(1) sletning. .

## Et praktisk eksempel: insert, delete, getRandom — alle O(1)

Krav: `insert(x)`, `remove(x)` og `getRandom()` hver i O(1). Et hash map alene kan ikke gøre O(1) random; et array alene kan ikke gøre O(1) sletning. **Kombiner dem**.

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

## Et generelt designopskrift

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

| Mønster | Kombinerede strukturer | Muliggør |
|---|---|---|
| LRU cache | hash map + dobbeltkædet linked list | O(1) get/put |
| O(1) randomiseret sæt | hash map + array | O(1) insert/remove/random |
| Min i O(1) på en stack | stack + hjælpe min-stack | O(1) getMin |

## Hvorfor det betyder noget

RigtigenSysteme har sjældent brug for en enkelt lærebogs-struktur — de har brug for en komposition, der er afstemt til et specifikt adgangsmønster, hvilket er præcis det, disse designs leverer.

Interviewere bruger disse problemer til at teste, om du kan ræsonnere fra **operationsomkostninger til en komposition**, kernekompetencen bag højperformance-systemdesign.

Mønster	Kombinerede strukturer	Muliggør
LRU cache	hash map + dobbeltkædet linked list	O(1) get/put
O(1) randomiseret sæt	hash map + array	O(1) insert/remove/random
Min i O(1) på en stack	stack + hjælpe min-stack	O(1) getMin