Random set
Design a data structure supporting insert(x), remove(x), and getRandom(), each in average O(1) time, where getRandom returns a uniformly random current element. Insert returns True if the value was newly added (False if already present); remove returns True if the value was present and removed (False otherwise). To make the result deterministic for grading, getRandom is replaced by getAt(i) which returns the element currently stored at internal slot i of the backing array (0-indexed). Given a list of operations (each a list like ['insert', 3], ['remove', 3], ['getAt', 0]), return the list of results in order. There are 1 to 10^4 ops; values fit in 32-bit signed range.
run_random_set(ops: list[list]) → list[[["insert",1],["remove",2],["insert",2],["getAt",1],["remove",1],["insert",2],["getAt",0]]]out[true,false,true,2,true,false,2]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[["insert",1],["remove",2],["insert",2],["getAt",1],["remove",1],["insert",2],["getAt",0]]][true,false,true,2,true,false,2]not run yetsample