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.
This problem asks for a data structure that supports insert, delete, and getRandom in average O(1) time. The standard solution combines a dynamic array for O(1) random access with a hash map that stores each id’s index in the array. Deletion is handled by swapping the target element with the last element and popping from the end, which avoids linear-time shifting and keeps all three operations efficient.
