TikTok 面试题 #8 —— 设计 O(1) 插入/删除/查找/随机取数的数据结构｜哈希表+动态数组｜tiktok 面经｜面试辅助

Problem (verbatim)

Design a data structure that supports insert, delete, search, and getRandom in constant time.

简单总结（思路要点）

• 用 动态数组（list/vector）+ 哈希表（value → index）。
• insert(x)：若不存在，将 x 追加到数组末尾，并在哈希表记录 x → lastIndex。
• search(x)：查哈希表是否存在。
• delete(x)：O(1) 删除关键：把 x 在数组中的位置与“数组最后一个元素”交换；更新该最后元素在哈希表中的索引；再 pop_back()；从哈希表移除 x。
• getRandom()：从 [0..size-1] 之间均匀随机生成索引，返回数组该位置元素。
• 复杂度：四个操作 均摊 O(1)；空间 O(n)。
• 关键陷阱：删除时一定要 先更新被交换元素的索引 ，再弹出末尾，确保一致性与均匀随机性。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Tiktok、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。