Design a Data Structure with Insert, Remove, and GetRandom for Unique Elements in O(1)
Design a data structure that supports three operations, all in average O(1) time: - insert(val): adds val to the data structure if not already present - remove(val): removes val if present - getUnique(): returns a uniformly random element that has been inserted exactly once (i.e., never re-inserted after removal) For example, after insert(1), insert(2), insert(1): getUnique() must return 2, since 1 was inserted more than once. After remove(1), both 1 and 2 are unique again, so getUnique() may return either.
Asked at:
Nebuis
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid July, 2026
Nebuis
Senior
Design a data structure that supports insert, remove, and getUnique operations, all in average O(1) time. The insert(val) adds an element if not present, remove(val) deletes an element if present, and getUnique() returns a random unique element from the current set. A element is considered unique if it has only been added to the set once. For example, after inserting 1, 2, 1. Calling getUnique() should return 2 as it is the only element which is unique. Input: ``` insert(1) → true insert(2) → true insert(1) → true getUnique() → 2 remove(1) → true getUnique() → 1 or 2 ``` **Output:** ``` true, true, true, 2, true , 1 or 2 ``` **Explanation:** First two inserts add unique elements, third adds 1 again and makes it no longer unique. getUnique returns 2 as it is the only element that is unique. After removing 1, both 1 and 2 are unique again. **Constraints:** * Values are integers within standard 32-bit range * Each operation must run in average O(1) time
Hello Interview Premium
Your account is free and you can post anonymously if you choose.