Insert Random
Medium · Onsite · Internship
After my project discussion, they gave me a data structure design problem. I had to support insert, delete, and getRandom in O(1). The interviewer cared about how I handled deletes without making random retrieval slower. I talked through the tradeoff between a list and a hashmap, then dry ran a few operations to make sure the indices stayed correct.
