Design a Set with $O(1)$ `insert`, `remove`, and `getRandom`

To achieve O(1) for insert, remove, and getRandom, I would combine a dynamic array with a hash map. The array allows us to access any element by index in constant time, which solves the getRandom requirement. However, removing an arbitrary element from an array usually takes O(n) because we must shift subsequent elements. To avoid this, we use the hash map to store the index of every value currently in the set. For insertion, we simply append the new value to the end of the array and record its index in the map. For removal, instead of shifting elements, we swap the target value with the last element in the array. We then pop the last element and update the map entry for the swapped value to reflect its new index. Finally, getRandom just generates a random integer between zero and the array size minus one and returns the element at that index. This approach ensures that no matter how many elements we have, all operations rely only on direct indexing or hash lookups, maintaining O(1) performance. This technique demonstrates the kind of optimization Google values: solving complex constraints through clever structural combinations rather than brute force.