Insert Delete GetRandom
Medium · Phone screen · Onsite · Full-time
This came up in my Okta technical round. Design a set that supports insert, remove, and getRandom all in O(1). The trick is using an array for the actual elements and a hash map from value to index, then swapping the element to remove with the last element before popping. The interviewer was really focused on the getRandom uniformity guarantee and asked what breaks if you use a linked list instead of an array.
