Startup OA 面试真题解析：Insert Delete GetRandom in O(1)｜哈希表与数组

We are designing a system for officers to check out a body worn camera from a pool of available cameras. We need an object to store a collection of camera ids, and our checkout system needs to get a random id out of this collection when an officer wants to check out a camera to use for their shift. When cameras are checked in, we need to insert the id into the pool, and when they are checked out, they need to be removed. Let’s use integers to represent the camera ids.

We will need to be able to insert and remove ids, so we need APIs for those operations. We also need an API to be able to get a random id from within the collection.

Some agencies can be very large, and shifts can overlap, so these 3 APIs are going to be used very often, and we want to be able to fill the collection with a very large set of ids. Because we want the checkout/checkin operations to be quick, we want to optimize this structure for performance. Our goal is to get average time complexity to“constant time”(i.e. O(1)) for each of these 3 operations.

class CameraPool:
    def __init__(self):
        pass

    def insert(self, id: int) -> bool:
        pass

    def remove(self, id: int) -> bool:
        pass

    # Gets random id from pool
    def select_random(self) -> int:
        pass

这道题本质上是经典的“支持插入、删除和随机返回元素，并且都要接近 O(1)”的数据结构设计题。最优解通常是“数组 + 哈希表”的组合：数组负责按下标存储元素，方便用随机下标直接取值；哈希表记录每个 id 在数组中的位置，方便在删除时用“末尾元素覆盖待删位置，再弹出末尾”的方式实现 O(1) 删除。若题目要求返回随机元素，则直接对数组做随机下标采样即可。