Å designe en tilpasset struktur betyr å kombinere eksisterende strukturer slik at hver påkrevd operasjon oppnår sin målkompleksitet, og lar en struktur dekke svakheten til en annen. Den klassiske teknikken er å pare et hash-kart med en array, heap eller koblet liste.
Krav: , og hver i O(1). Et hash-kart alene kan ikke gjøre O(1) random; en array alene kan ikke gjøre O(1) remove. .
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.
| Mønster | Kombinerte strukturer | Muliggjør |
|---|---|---|
| LRU cache | hash-kart + dobbeltlenket liste | O(1) get/put |
| O(1) randomisert mengde | hash-kart + array | O(1) insert/remove/random |
| Min i O(1) på en stack | stack + hjelpestabel min-stack | O(1) getMin |
Ekstesystemer trenger sjelden en enkelt lærebokstruktur — de trenger en kombinasjon optimalisert for et spesifikt tilgangsmønster, som er nettopp det disse designene leverer.
Intervjuere bruker disse oppgavene til å teste om du kan resonnere fra operasjonskostnader til en kombinasjon, kjernekunnskapen bak høyytelsessystemdesign.