O(1) Insert Delete Random Set

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is O(1) Insert Delete Random Set. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output