O(1) Insert Delete Random Set

MediumPython00:00

Practice interviewer

Your interviewer

In session

Interviewer

Welcome to the Python screen.

The question is on your right: O(1) Insert Delete Random Set. Read through the requirements first.

Run and submit your code as often as you need. You also have five interviewer messages this session - want to talk through your approach, or are you ready to start coding?

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