Hur designar du en datastruktur med specifika O(1)/O(log n)-krav?

Question

IT Interview Practice · Accepted Answer

Att designa en anpassad struktur innebär att **kombinera befintliga strukturer** så att varje obligatorisk operation når sin målkomplexitet, där en struktur täcker en annan svaghet. Den klassiska tekniken är att para ihop en **hash-tabell** med en **array, heap eller länkad lista**.

## Ett praktiskt exempel: insert, delete, getRandom — alla O(1)

Krav: `insert(x)`, `remove(x)` och `getRandom()` var och en i O(1). En hash-tabell ensam kan inte göra O(1) randomisering; en array ensam kan inte göra O(1) borttagning. **Kombinera 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)
```

## En allmän designrecept

```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 | Kombinerade strukturer | Möjliggör |
|---|---|---|
| LRU-cache | hash-tabell + dubbelt länkad lista | O(1) get/put |
| O(1) randomiserad mängd | hash-tabell + array | O(1) insert/remove/random |
| Min i O(1) på en stack | stack + hjälpmin-stack | O(1) getMin |

## Varför det spelar roll

Riktiga system behöver sällan en enda lärobok-struktur — de behöver en komposit anpassad till ett specifikt åtkomstmönster, vilket är exakt vad dessa designer levererar.

Intervjuare använder dessa problem för att testa om du kan resonera från **operationskostnader till en komposition**, kärnfärdigheten bakom högtpresterande systemdesign.

Mönster	Kombinerade strukturer	Möjliggör
LRU-cache	hash-tabell + dubbelt länkad lista	O(1) get/put
O(1) randomiserad mängd	hash-tabell + array	O(1) insert/remove/random
Min i O(1) på en stack	stack + hjälpmin-stack	O(1) getMin

Ett praktiskt exempel: insert, delete, getRandom — alla O(1)

En allmän designrecept

Varför det spelar roll

Relaterade frågor