Constant-Time Put, Delete and Uniform Random Selection Data Structure

Design a data structure that supports `put`, `delete`, and `getRandom`, each in O(1) time. For the core version, assume the structure stores a set of distinct keys: `put(key)` inserts `key` if it is not already present, `delete(key)` removes `key` if it is present, and `getRandom()` returns one of the currently stored keys, with every stored key equally likely. Confirm the remaining semantics with the interviewer (see the clarifying questions), then implement the structure and justify the complexity of each operation. ```hint Match each operation to a capability One operation needs to find an element by its value; another needs to pick a uniformly random position. Consider which structures provide each, and what removing an element does to the second capability. ``` ### Constraints and Clarifications - O(1) may mean expected constant time for operations that rely on hashing; state explicitly which bounds are expected, which are amortized, and which are worst case. - `getRandom` must be uniform over the keys stored at the moment of the call, regardless of the order or history of earlier insertions and deletions. - Keys are hashable values that can be compared for equality. ### Clarifying Questions - Does `put` take only a key, or a key and a value, and what should `getRandom` return in the key-value case? - Can the same key be added more than once, and if so, should each extra occurrence make that key more likely to be returned? - What should `delete` do for an absent key, and what should `getRandom` do when the structure is empty? - Will the structure be accessed by multiple threads at once? ### What a Strong Answer Covers - A layout that supports lookup by value and uniform selection by position at the same time, with an invariant linking the two. - A deletion procedure that preserves the invariant in constant time, with correctness argued for the element stored at the last position. - Precise complexity claims (expected versus amortized versus worst case) and space usage. - Handling of the clarified semantics: key-value storage, duplicates, absent keys, and the empty structure. ### Follow-up Questions 1. How would you change the design if duplicates are allowed and every occurrence must be equally likely to be returned? 2. How would you support `getRandom` weighted by a per-key weight, and what would the operation costs become? 3. How would you make the structure safe for concurrent use without forcing every `getRandom` call through one exclusive lock?