การออกแบบโครงสร้างแบบกำหนดเอง หมายถึง การรวมโครงสร้างที่มีอยู่ เพื่อให้ทุกการดำเนินการที่จำเป็นบรรลุความซับซ้อนของเป้าหมาย โดยโครงสร้างหนึ่งครอบคลุมจุดอ่อนของอีกโครงสร้างหนึ่ง เทคนิคแบบดั้งเดิมคือการจับคู่ 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 ใน O(1) บน stack | stack + auxiliary min-stack | O(1) getMin |
ระบบจริงแทบจะไม่จำเป็นต้องใช้โครงสร้างตำราเรียนเพียงชิ้นเดียว — พวกมันต้องการองค์ประกอบผสมที่ปรับให้เหมาะกับรูปแบบการเข้าถึงเฉพาะ ซึ่งนี่คือสิ่งที่การออกแบบเหล่านี้มอบให้อย่างแน่นอน
ผู้สัมภาษณ์ใช้ปัญหาเหล่านี้เพื่อทดสอบว่าคุณสามารถใช้เหตุผลจาก ต้นทุนการดำเนินการไปยังองค์ประกอบผสม ซึ่งเป็นทักษะพื้นฐานเบื้องหลังการออกแบบระบบประสิทธิภาพสูง