Constant-Time Put, Delete and Uniform Random Selection Data Structure
Company: Goldman Sachs
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: easy
Interview Round: Onsite
Overview: Design a data structure that inserts a key, deletes a key, and returns a uniformly random stored key, with every operation in constant time. It tests combining complementary structures, preserving an index invariant during deletion, precise expected versus amortized complexity claims, and handling of duplicates and an empty structure.