Návrh vlastní struktury znamená kombinování existujících struktur tak, aby každá požadovaná operace dosáhla své cílové složitosti, což umožňuje jedné struktuře pokrýt slabinu jiné. Klasickou technikou je spojení hash mapy s polem, haldou nebo propojeným seznamem.
Požadavky: , a každá v O(1). Hash mapa sama nemůže dosáhnout O(1) náhodnosti; pole samo nemůže dosáhnout O(1) odstranění. .
insert(x)remove(x)getRandom()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)
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.
| Vzor | Kombinované struktury | Umožňuje |
|---|---|---|
| LRU cache | hash mapa + obousměrný propojený seznam | O(1) get/put |
| O(1) randomizovaná sada | hash mapa + pole | O(1) insert/remove/random |
| Min v O(1) na zásobníku | zásobník + pomocný min-stack | O(1) getMin |
Skutečné systémy zřídka potřebují jednu textbookovou strukturu — potřebují kompozici vyladěnou na specifický vzor přístupu, což je přesně to, co tyto návrhy poskytují.
Intervieweři používají tyto problémy k testování, zda dokážete uvažovat od nákladů operací k kompozici, základní dovednost za návrhem vysoce výkonných systémů.