usrbinenv python3 design a data structure that supports all following operations in average o1 time insertval inserts an item val to the set if not already present removeval removes an item val from the set if present randomelement returns a random element from current set of elements each element must have the same probability of being returned idea shoot remove a half usr bin env python3 design a data structure that supports all following operations in average o 1 time insert val inserts an item val to the set if not already present remove val removes an item val from the set if present random_element returns a random element from current set of elements each element must have the same probability of being returned idea shoot element index remove a half
import random


class RandomizedSet():
    

    def __init__(self):
        self.elements = []
        self.index_map = {}  

    def insert(self, new_one):
        if new_one in self.index_map:
            return
        self.index_map[new_one] = len(self.elements)
        self.elements.append(new_one)

    def remove(self, old_one):
        if not old_one in self.index_map:
            return
        index = self.index_map[old_one]
        last = self.elements.pop()
        self.index_map.pop(old_one)
        if index == len(self.elements):
            return
        self.elements[index] = last
        self.index_map[last] = index

    def random_element(self):
        return random.choice(self.elements)


def __test():
    rset = RandomizedSet()
    ground_truth = set()
    n = 64

    for i in range(n):
        rset.insert(i)
        ground_truth.add(i)

    
    for i in random.sample(range(n), n // 2):
        rset.remove(i)
        ground_truth.remove(i)

    print(len(ground_truth), len(rset.elements), len(rset.index_map))
    for i in ground_truth:
        assert(i == rset.elements[rset.index_map[i]])

    for i in range(n):
        print(rset.random_element(), end=' ')
    print()


if __name__ == "__main__":
    __test()