Insert Delete GetRandom O(1) - Duplicates allowed

Insert Delete GetRandom O(1) - Duplicates allowed

1. What is this problem about?

The Insert Delete GetRandom O(1) - Duplicates allowed interview question is a high-level data structure design challenge. You need to implement a class that stores integers and allows for duplicates. The structure must support insert, remove, and getRandom (which picks an element with probability proportional to its frequency) all in constant $O(1)$ average time.

2. Why is this asked in interviews?

Companies like Meta, Amazon, and Uber ask the Duplicates allowed coding problem to see if a candidate can handle complex updates in a multi-mapped environment. It tests your proficiency with Hash Table interview patterns and your ability to manage pointers/indices within a dynamic array. It’s a rigorous evaluation of your understanding of amortized time complexity and uniform probability distribution.

3. Algorithmic pattern used

This problem uses a Hash Map of Indices + Dynamic Array pattern.

• The Array: Stores all instances of every value to ensure getRandom remains $O(1)$ and uniform.
• The Map: Maps each Value -> Set of Indices where that value appears in the array.
• Constant Time Removal: When removing a value, pick any index from its set in the map. Use the "Swap with Last" trick: swap the element at that index with the last element in the array, update the last element's index in the map, and then remove the target index.

4. Example explanation

Current elements: [1, 1, 2]. Array: [1, 1, 2], Map: {1: {0, 1}, 2: {2}}.

• insert(1): Array becomes [1, 1, 2, 1], Map: {1: {0, 1, 3}, 2: {2}}.
• remove(2):
  • 2 is at index 2. Last element is 1 at index 3.
  • Swap: Array becomes [1, 1, 1, 2].
  • Update Map: 1's set now has {0, 1, 2}, 2 is popped.
• getRandom(): Any index from 0 to 2 is picked with 1/3 probability. 1 has a 2/3 chance, 2 has a 0 chance (removed).

5. Common mistakes candidates make

• Probability Skew: Using a Hash Map alone and picking a random key. This makes all unique values equally likely, rather than all instances.
• Inefficient Deletion from Set: Using a list of indices instead of a hash set, which makes finding and removing a specific index $O(N)$ instead of $O(1)$.
• Map Desync: Forgetting to update the index of the element that was "moved" to fill the gap during deletion.

6. Interview preparation tip

Focus on the Probability requirement. Uniform probability over elements means every slot in the storage array must be equally likely to be picked. If a value appears twice, it should occupy two slots.