Insert Delete GetRandom O(1): Data Structure รองรับ Insert, Delete, GetRandom ใน O(1)

โจทย์

ออกแบบ Data Structure รองรับ operations ทั้ง 3 ใน Average O(1):

• insert(val): เพิ่ม val ถ้ายังไม่มี → True, ถ้ามีแล้ว → False
• remove(val): ลบ val ถ้ามี → True, ถ้าไม่มี → False
• getRandom(): คืนค่า random element จากชุดปัจจุบัน (ทุก element โอกาสเท่ากัน)

วิธีแก้: Array + Hash Map (Index Mapping)

• Array (list): เก็บ elements รองรับ getRandom ด้วย random.choice() O(1)
• Hash Map (dict): val → index ใน array รองรับ insert/remove/lookup O(1)
• Trick การลบ O(1): Swap with last element แล้ว pop()

การติดตั้ง (Python Implementation)

import random

class RandomizedSet:
    def __init__(self):
        self.val_to_index = {}  # val -> index in array
        self.elements = []      # array of values
    
    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.val_to_index[val] = len(self.elements)
        self.elements.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        
        idx = self.val_to_index[val]
        last_val = self.elements[-1]
        
        # Swap with last element
        self.elements[idx] = last_val
        self.val_to_index[last_val] = idx
        
        # Remove last
        self.elements.pop()
        del self.val_to_index[val]
        return True
    
    def getRandom(self) -> int:
        return random.choice(self.elements)

# ทดสอบ
ob = RandomizedSet()
print(ob.insert(1))    # True
print(ob.remove(2))    # False
print(ob.insert(2))    # True
print(ob.getRandom())  # 1 or 2 (random)
print(ob.remove(1))    # True
print(ob.insert(2))    # False (already exists)
print(ob.getRandom())  # 2

Output

True
False
True
1 (or 2)
True
False
2

การทำงานของ Remove (Swap with Last)

Before remove(1): elements=[1,2], map={1:0, 2:1}
idx=0, last_val=2
Swap: elements[0]=2, map[2]=0
Pop: elements=[2], map={2:0}
Result: elements=[2], map={2:0} ✓

Complexity

• insert: O(1) average (dict + list append)
• remove: O(1) average (dict lookup + swap + pop)
• getRandom: O(1) (random.choice on list)
• Space: O(n)

ข้อควรระวัง

• random.choice() ต้องการ list ที่ไม่ว่าง (handle empty case)
• Swap technique ทำให้ index ของ last element เปลี่ยน → ต้อง update map ด้วย
• Python dict insertion order preserved (3.7+) แต่ไม่เกี่ยวกับ logic นี้

สรุป

Insert Delete GetRandom O(1) เป็นโจทย์คลาสสิก ใช้ Array + Hash Map (Index Mapping) พร้อมเทคนิค Swap with Last สำหรับ remove O(1) รูปแบบนี้ใช้ได้หลายที่ เช่น RandomizedSet, LRU Cache variants, etc.

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ