მორგებული სტრუქტურის დიზაინი ნიშნავს არსებული სტრუქტურების კომპოზიციას ისე, რომ თითოეული საჭირო ოპერაცია მიაღწიოს თავის სამიზნე კომპლექსობას, ერთი სტრუქტურა დაფაროს მეორის სუსტი მხარე. კლასიკური ტექნიკა არის hash map-ის პაირინგი array-სთან, heap-თან ან linked list-ის.
მოთხოვნები: , და თითოეული O(1)-ში. Hash map-ი혼자 არ შეუძლია O(1) random-ის გაკეთება; array არ შეუძლია 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.
| შაბლონი | კომბინირებული სტრუქტურები | ამჯობინებს |
|---|---|---|
| LRU cache | hash map + doubly linked list | O(1) get/put |
| O(1) randomized set | hash map + array | O(1) insert/remove/random |
| Min in O(1) on a stack | stack + auxiliary min-stack | O(1) getMin |
ბერძენი სისტემები ხშირად არ საჭიროებენ ერთ სახელმძღვანელო სტრუქტურას — მათ საჭიროებთ კომპოზიტი, რომელიც მორგებულია კონკრეტული წვდომის ნიმუშზე, რაც ზუსტად ის არის, რასაც ეს დიზაინი გვაძლევს.
ინტერვიუერები იყენებენ ამ პრობლემებს იმის შესამოწმებლად, შეგიძლიათ თუ არა მსჯელობა ოპერაციების ხარჯებიდან კომპოზიციამდე, რაც მაღალი წარმადობის სისტემის დიზაინის უმთავრესი უნარი.