Build a data structure supporting insert(val), remove(val), and getRandom(), each in average time. Amazon asks this to test your ability to combine data structures.
insert(val) adds the item if not present, returning true or false. remove(val) removes if present, returning true or false. getRandom() returns a random element with equal probability.
After insert(1) and insert(2), getRandom() returns either or . After remove(1), getRandom() always returns .
Think about which data structures give you lookup and which give you random access. Can you combine them?