Proiectarea unei structuri personalizate înseamnă compunerea structurilor existente astfel încât fiecare operație cerută să atingă complexitatea țintă, permițând unei structuri să acopere slăbiciunea alteia. Tehnica clasică este asocierea unei hash map cu un array, heap, sau linked list.
Cerințe: , , și fiecare în O(1). O hash map singură nu poate face O(1) random; un array singur nu poate face 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.
| Pattern | Structuri combinate | Permite |
|---|---|---|
| LRU cache | hash map + doubly linked list | O(1) get/put |
| Set randomizat O(1) | hash map + array | O(1) insert/remove/random |
| Min în O(1) pe un stack | stack + auxiliary min-stack | O(1) getMin |
Sistemele reale rar au nevoie de o singură structură din manuale — au nevoie de o compunere ajustată la un model de acces specific, ceea ce este exact ceea ce oferă aceste proiecte.
Intervievatorii folosesc aceste probleme pentru a testa dacă poți să raționezi din costuri de operații la o compunere, abilitatea de bază din spatele proiectării sistemelor de înaltă performanță.