Pasirinktinės struktūros projektavimas reiškia esamų struktūrų sujungimą taip, kad kiekviena reikalinga operacija pasiektu savo tikslinę sudėtingumą, o viena struktūra užddengtų kitos silpnybę. Klasikinis būdas — sujungti hash žemėlapį su masyvu, gūla arba susieta sąrašu.
Reikalavimai: , ir kiekvienas O(1). Hash žemėlapis vienas negali O(1) atsitiktinybės; masyvai vienas negali O(1) šalinti. .
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.
| Šablonas | Sujungtos struktūros | Leidžia |
|---|---|---|
| LRU cache | hash žemėlapis + dvikryptis susietas sąrašas | O(1) get/put |
| O(1) randomized set | hash žemėlapis + masyvai | O(1) insert/remove/random |
| Min in O(1) on a stack | stack + pagalbinis min-stack | O(1) getMin |
Tikrų sistemų retai reikia viena vadovaičio struktūra — joms reikia junginys, pritaikytas konkrečiam prieigos modeliui, kuri yra būtent tai, ką šie projektai teikia.
Interviu klausūs naudoja šias problemas bandydami patikrinti, ar jūs galite samprotauti nuo operacijos sąmatų iki junginio, yra pagrindinį įgūdžiu dėl didelio našumo sistemos projektavimo.