Startup Coding Interview Question: 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

This is a classic data structure design problem: support insert, delete, and getRandom in average O(1) time. The standard solution combines a dynamic array with a hash map. The array stores the ids so a random element can be picked by index, while the hash map tracks each id’s position for constant-time lookup and deletion. To remove an element efficiently, swap it with the last element in the array, update the index map, and pop from the end.