RandomizedSet
Medium · Phone screen · Onsite · Full-time
Got a design question where I had to implement a RandomizedSet class supporting insert, remove, and getRandom, all in average O(1). The trick is pairing a hash map with an array so you can do constant-time lookups and still pick a random element by index. The swap-to-end trick for remove was the key insight they were looking for. The interviewer also asked what would break if I used a linked list instead of an array.
