O(1) insert, remove, contains and get_random

problem_solution_1.py

import random

class MyDataStructure(object):

    def __init__(self):
        self.d = {} # hash table
        self.li = [] # dynamic resizing array

    def insert(self, key):
        if key in self.d:
            index = self.d[key]
            self.d[key] = index
            self.li[index] = key
        else:
            self.d[key] = len(self.li)
            self.li.append(key)

    def remove(self, key):
        if key in self.d:
            index = self.d[key] # get the index for the key
            last_key = self.li[-1] # the key for the last element in the list
            self.li[index] = last_key # set it in the index which you want to remove

            # update the hashtable to reflect this index change
            old_index = self.d[last_key]
            self.d[last_key] = index

            # proceed to delete the entry
            del self.d[key]
            self.li.pop()

    def contains(self, key):
        return key in self.d

    def get_random(self):
        length = len(self.li)
        key = self.li[random.randrange(length)]
        return key

if __name__ == '__main__':
    ds = MyDataStructure()
    ds.insert('Hen')
    ds.insert('Donkey')
    ds.insert('Pig')

    print "Debug 1: ", ds.d, ds.li

    for _ in range(4):
        print ds.get_random()

    ds.remove('Hen')

    print "Debug 2: ", ds.d, ds.li