O(1) Insert Delete Random Set | Dataford Interview Questions

Design a data structure that supports insert(val), remove(val), and get_random() in average O(1) time. insert(val) adds an integer if it is not already present and returns a boolean indicating success. remove(val) deletes the integer if present and returns a boolean. get_random() returns one element currently stored, where each element must have equal probability of being chosen.

Constraints

0 <= val <= 10^9
1 <= len(operations) <= 2 * 10^5
len(operations) == len(values)
Each operation is one of 'insert', 'remove', or 'get_random'
get_random() is only called when the structure is non-empty

Function Signature

def randomized_set(operations, values):

Your question is O(1) Insert Delete Random Set. 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

Constraints

0 <= val <= 10^9
1 <= len(operations) <= 2 * 10^5
len(operations) == len(values)
Each operation is one of 'insert', 'remove', or 'get_random'
get_random() is only called when the structure is non-empty

Function Signature

def randomized_set(operations, values):

Your question is O(1) Insert Delete Random Set. 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.