Insert Delete GetRandom O(1) - Duplicates allowed

Insert Delete GetRandom O(1) - Duplicates allowed

1. What is this problem about?

This is the "Hard" version of the randomized set problem. You must support insert, remove, and getRandom in $O(1)$, but the set can now contain duplicate values. Each instance of a value must have an equal probability of being returned by getRandom().

2. Why is this asked in interviews?

Companies like Citadel and Peloton ask the Insert Delete GetRandom O(1) - Duplicates allowed coding problem to see if a candidate can handle complex state management. It requires a Hash Table interview pattern where the value maps to a set of indices, making the "Swap and Pop" logic significantly more complex to maintain.

3. Algorithmic pattern used

This uses a Hash Map of Sets + Dynamic Array.

• Map<Integer, Set<Integer>>: Maps each value to a set of all indices where that value appears in the array.
• ArrayList<Integer>: Stores the values.
• Deletions: When removing val, pick any index from map.get(val). Swap the element at that index with the very last element in the array, update the last element's set in the map to reflect its new index, and then remove the original index from val's set.

4. Example explanation

Array: [10, 10, 20]. Map: {10: {0, 1}, 20: {2}}.

• remove(10):
  • Pick index 0.
  • Last element is 20 at index 2.
  • Move 20 to index 0. Array: [20, 10, 20].
  • Update 20's indices: {20: {0}}.
  • Pop last: Array: [20, 10].
  • Remove index 0 from 10's set: {10: {1}}.

5. Common mistakes candidates make

• Removing the wrong index: Updating the map for the deleted value but forgetting to update it for the "moved" last element.
• Set Inefficiency: Using a list of indices instead of a hash set, which could make removing a specific index $O(N)$.
• Uniformity: Failing to ensure that duplicates increase the chance of that value being picked in getRandom. (The array naturally handles this if each instance has its own slot).

6. Interview preparation tip

Practice using "Multimaps" or "Map of Sets." In design problems, adding duplicates usually means transforming a Value -> Data mapping into a Value -> Collection<Data> mapping.