Insert Delete GetRandom O(1)

Problem

Simulate a set supporting insert, remove, and get_random in O(1) average time.

operations contains "insert" (values[i]), "remove" (values[i]), or "get_random". insert returns False when the value is already present and True otherwise; remove returns True when the value was present and False otherwise. get_random uses random.Random(0) so results are reproducible, and returns None for an empty set.

Return the list of recorded results.

Hint

Removing in O(1) swaps the value with the last element before popping, fixing the position map.

Test cases

case 1

in: [["insert","insert","remove","insert","get_random"],[1,2,2,2,0]]

expected: [true,true,true,true,2]

case 2

in: [["remove","get_random"],[5,0]]

expected: [false,null]

case 3

in: [["insert","insert","insert","get_random","get_random"],[1,2,3,0,0]]

expected: [true,true,true,2,2]

case 4

in: [["insert","insert"],[1,1]]

expected: [true,false]

Starter codePython

def insert_delete_random(operations, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor