Özel bir yapı tasarlamak, mevcut yapıları birleştirerek her gerekli işlemin hedef karmaşıklığına ulaşmasını sağlamak anlamına gelir; bir yapı diğerinin zayıflığını telafi eder. Klasik teknik, bir hash map ile array, heap veya linked list 'i eşleştirmektir.
Gereksinimler: , ve her biri O(1) içinde. Hash map yalnız O(1) rastgele yapamaz; array yalnız O(1) silme yapamaz. .
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.
| Desen | Birleştirilen yapılar | Sağlar |
|---|---|---|
| LRU cache | hash map + doubly linked list | O(1) get/put |
| O(1) rastgeleleştirilmiş set | hash map + array | O(1) insert/remove/random |
| Stack'te O(1) Min | stack + auxiliary min-stack | O(1) getMin |
Gerçek sistemler nadiren tek bir ders kitabı yapısına ihtiyaç duyar — belirli bir erişim desenine göre ayarlanmış bir bileşime ihtiyaç duyar, ki bu tam olarak bu tasarımların sunduğu şeydir.
Mülakatçılar bu problemleri, işlem maliyetlerinden bir bileşime akıl yürütüp yürütemeyeceğinizi test etmek için kullanır. Bu, yüksek performanslı sistem tasarımının arkasında yatan temel beceridir.