Design a data structure that supports all following operations in *average* **O(1)** time.

`insert(val)`

: Inserts an item val to the set if not already present.`remove(val)`

: Removes an item val from the set if present.`getRandom`

: Returns a random element from current set of elements. Each element must have the**same probability**of being returned.

**Discussion:**

In C++, containers supporting insert with O(1) are *vector*, *list*, *unordered_map*, and *unordered_set*.

Containers remove by value with O(1) are *unordered_map*, *unordered_set*.

Container supporting random access is *vector*.

So, we can use *vector* AND *unordered_set* or *unordered_map* for the three functions. Then *unordered_set* or *unordered_map*? We have to use *vector* to store the values for the sake of random access with O(1). And a hash container (*unordered_set*, or *unordered_map*) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so *unordered_map* wins: reference the same value in the *vector* by the value’s position.

insert and random access can easily being done with O(1) for *vector* and *unordered_map*. But for remove, it affects the *unordered_map*‘s reference in the vector. The instinct is removing the value from the *vector* by getting its position from *unordered_map*. But this will decrease the positions of all descending elements in the *vector*, which affects the references of the *unordered_map*. The time complexity could be up to linear O(n) if we do position update in the *unordered_map*, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the *vector*, and updating the last element’s value in the *unordered_map* with the new position. exactly O(1) on average.