Here is solutions for Randomized Camera Checkout by Id - Constant Time.

1. Understand the problem

✅ 1. Understand the Problem

• We are building a camera checkout pool that stores camera IDs (integers) and supports:

  • insert(id) → add a camera back to the pool

  • remove(id) → remove a camera when it’s checked out

  • select_random() → return a random available camera ID

• Requirements:

  • These operations will be called very frequently

  • The pool can be very large

  • Duplicates ARE allowed (senior-level add-on)

  • We must achieve O(1) average time for:

    • Insert

    • Remove

    • Get Random

• So this is a high-performance randomized data structure problem.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Edge cases to consider

1. What happens if “GetRandom” API is called when collection is empty They will typically note here that the return type of “int” is unsuitable. Ask what the options are assuming the API is set in stone. (Good answer: Throw an exception/abort. Bad answer: Just reserve some integers, like 0, that can’t be put in the collection).

2. What happens if remove is called on the last element in the collection

3. What happens if I try and remove an integer that is not in the collection

4. What happens if I try to insert the same integer twice

3. Explore examples.

1. Example 1

insert(10)
insert(20)
insert(10)
insert(30)

Pool = [10, 20, 10, 30]

1. Example 2

remove(10)

• Only one 10 is removed:

• Pool could become: [30, 20, 10]

1. Example 3

• remove(99) → False

• remove(20) → True

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Naive (List Only)

• Use a list:

  • Insert → append → O(1)

  • Random → random.choice → O(1)

  • Remove → list.remove(id) → O(n) (linear scan)

4.2. 🟡 Solution 2: HashMap Only

id → count

• Insert → O(1)

• Remove → O(1)

❌ Random → Not possible in O(1), because:

- You don’t know how many total values exist

- You can’t directly pick a random occurrence

❌ Fails random selection requirement

4.3. Solution 3: Optimized O(1)

We need:

• Random access → use a list

• Fast lookup/removal with duplicates → use a hashmap of index sets

Data Structures:

- arr: dynamic list of all values

- pos: hashmap → id -> set of indices in arr

Why This Works:

• Random selection → random index in arr

• Insert → append to arr, store index in pos

• Remove → use swap-with-last trick to delete in O(1)

5. Implement solutions.

import random
from collections import defaultdict

class CameraPool:

    def __init__(self):
        self.arr = []                      # stores all camera ids
        self.pos = defaultdict(set)       # id -> set of indices

    def insert(self, id: int) -> bool:
        existed = id in self.pos and len(self.pos[id]) > 0

        self.arr.append(id)
        self.pos[id].add(len(self.arr) - 1)

        return not existed

    def remove(self, id: int) -> bool:
        if id not in self.pos or len(self.pos[id]) == 0:
            return False

        # Get one index of this id
        remove_idx = self.pos[id].pop()
        last_val = self.arr[-1]

        # Move last element to the removed spot
        self.arr[remove_idx] = last_val

        # Update last_val index set
        self.pos[last_val].add(remove_idx)
        self.pos[last_val].discard(len(self.arr) - 1)

        # Remove last element
        self.arr.pop()

        return True

    def select_random(self) -> int:
        return random.choice(self.arr)

• Idea: Xoá cái index cuối, lấy last_val gán vô cái remove idx.

6. Dry run testcases.

arr = [5, 10, 5, 20]

pos = {
  5: {0, 2},
  10: {1}
  20: {3}
}

• remove(5)

arr = [5, 10, 5, 20]

=> arr = [5, 10, 20, 20]

=> pop the last value => [5, 10, 20]

pos = {
  5: {0},
  10: {1}
  20: {2}
}

=> Remove default value in a dict O(1)