Merancang struktur khusus berarti menggabungkan struktur yang ada sehingga setiap operasi yang diperlukan mencapai target kompleksitasnya, memungkinkan satu struktur menutupi kelemahan struktur lain. Teknik klasik adalah memasangkan hash map dengan array, heap, atau linked list.
Persyaratan: , , dan masing-masing dalam O(1). Hash map saja tidak dapat melakukan O(1) random; array saja tidak dapat melakukan 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.
| Pola | Struktur yang digabungkan | Memungkinkan |
|---|---|---|
| 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 |
Sistem nyata jarang membutuhkan satu struktur buku teks — mereka membutuhkan komposit yang disesuaikan dengan pola akses tertentu, yang merupakan persisnya apa yang dirancang ini berikan.
Pewawancara menggunakan masalah-masalah ini untuk menguji apakah Anda dapat bernalar dari biaya operasi ke komposisi, keterampilan inti di balik desain sistem berkinerja tinggi.