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.
这道题的核心是设计一个支持高频插入、删除和随机获取的集合，并要求这三个操作都能做到均摊 O(1)。典型做法是用一个动态数组保存所有摄像头 id，这样可以 O(1) 随机访问；再用一个哈希表记录每个 id 在数组中的位置，方便 O(1) 定位删除。删除时用“末尾元素覆盖待删位置”的技巧，避免中间删除导致整体搬移，从而保持性能稳定。
