Randomized Get/Insert Structure | Dataford Interview Questions

Design a data structure supporting insert, delete, and getRandom in average O(1) time.

Asked in the Virtual Interview stage. Similar to LeetCode 380. Implement the unique-element version using the following grading wrapper:

randomized_set_operations(operations) receives a list of operations such as ["insert", 5], ["delete", 5], and ["getRandom"]. Return each operation's result in order. getRandom is tested only when exactly one element exists, so its result is deterministic.

Reported follow-up: How would you extend this data structure to support duplicate elements?

Constraints

1 <= operations.length <= 10^4
Each operation is ["insert", value], ["delete", value], or ["getRandom"]
-10^9 <= value <= 10^9
The set contains unique values
getRandom is called only when the set is non-empty

Function Signature

def randomized_set_operations(operations):

Your question is Randomized Get/Insert Structure. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem