TikTok 面試：設計支援 O(1) 操作的隨機集合資料結構

TikTok 面試中的經典資料結構設計題。本文通過隨機集合的實作，展示如何在常數時間內完成插入、刪除、搜尋和隨機獲取操作。oavoservice 助你掌握高階資料結構設計。

📋 問題重構

設計一個資料結構 RandomizedSet，支援以下操作，且所有操作的平均時間複雜度為 O(1)：

1. insert(val) - 插入元素，如果不存在返回 true
2. remove(val) - 刪除元素，如果存在返回 true
3. search(val) - 搜尋元素是否存在
4. getRandom() - 隨機返回集合中的一個元素

關鍵約束： 每個元素被隨機選中的機率必須相等。

🎯 核心挑戰

1. O(1) 插入和刪除 - 需要快速定位
2. O(1) 隨機獲取 - 需要支援索引訪問
3. 等機率隨機 - 確保公平
4. 空間效率 - 避免過多的記憶體開銷

💡 解題思路（oavoservice 創新方法）

方法：陣列 + 雜湊表（經典解法）

import random

class RandomizedSet:
    def __init__(self):
        self.data = []  # 存儲元素，支援隨機訪問
        self.index_map = {}  # {val: index} 支援 O(1) 查找
    
    def insert(self, val):
        if val in self.index_map:
            return False
        
        self.index_map[val] = len(self.data)
        self.data.append(val)
        return True
    
    def remove(self, val):
        if val not in self.index_map:
            return False
        
        # 與最後一個元素交換以實現 O(1) 刪除
        last_element = self.data[-1]
        idx_to_remove = self.index_map[val]
        
        self.data[idx_to_remove] = last_element
        self.index_map[last_element] = idx_to_remove
        
        self.data.pop()
        del self.index_map[val]
        return True
    
    def getRandom(self):
        return random.choice(self.data)

🚀 深度追問

Q1: 為什麼刪除時要交換？

oavoservice 解釋：

• 陣列中間刪除是 O(n)。
• 交換到末尾後刪除只需 O(1)。
• 不影響隨機性，因為順序不重要。

Q2: 如何保證隨機性的均勻分佈？

oavoservice 解釋：

• random.choice() 使用均勻分佈。
• 關鍵是保持陣列的連續性。

Q3: 如果允許重複元素怎麼辦？

oavoservice 建議：

• index_map 存儲索引集合：{val: {idx1, idx2}}。
• 這是 RandomizedCollection 變體。

💼 oavoservice 如何助力 TikTok 面試

多種解法 - 從基礎到進階的完整方案 權衡分析 - 不同方案的優劣對比 擴展討論 - 重複元素、加權等變體 程式碼優化 - 簡潔高效的實作

聯繫 oavoservice，專業資料結構面試輔助！

標籤： #TikTok #資料結構 #RandomizedSet #雜湊表 #VO輔助 #面試輔助 #一畝三分地

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。