Design a data structure that supports insert , delete , search and getRandom in constant time | Python program to design a DS that supports following operations in Theta ( n ) time : a ) Insertb ) Deletec ) Searchd ) getRandom ; Class to represent the required data structure ; Constructor ( creates a list and a hash ) ; A resizable array ; A hash where keys are lists elements and values are indexes of the list ; A Theta ( 1 ) function to add an element to MyDS data structure ; If element is already present , then nothing has to be done ; Else put element at the end of the list ; Also put it into hash ; A Theta ( 1 ) function to remove an element from MyDS data structure ; Check if element is present ; If present , then remove element from hash ; Swap element with last element so that removal from the list can be done in O ( 1 ) time ; Remove last element ( This is O ( 1 ) ) ; Update hash table for new index of last element ; Returns a random element from MyDS ; Find a random index from 0 to size - 1 ; Return element at randomly picked index ; Returns index of element if element is present , otherwise none ; Driver Code
import random NEW_LINE class MyDS : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . arr = [ ] NEW_LINE self . hashd = { } NEW_LINE DEDENT def add ( self , x ) : NEW_LINE INDENT if x in self . hashd : NEW_LINE INDENT return NEW_LINE DEDENT s = len ( self . arr ) NEW_LINE self . arr . append ( x ) NEW_LINE self . hashd [ x ] = s NEW_LINE DEDENT def remove ( self , x ) : NEW_LINE INDENT index = self . hashd . get ( x , None ) NEW_LINE if index == None : NEW_LINE INDENT return NEW_LINE DEDENT del self . hashd [ x ] NEW_LINE size = len ( self . arr ) NEW_LINE last = self . arr [ size - 1 ] NEW_LINE self . arr [ index ] , self . arr [ size - 1 ] = self . arr [ size - 1 ] , self . arr [ index ] NEW_LINE del self . arr [ - 1 ] NEW_LINE self . hashd [ last ] = index NEW_LINE DEDENT def getRandom ( self ) : NEW_LINE INDENT index = random . randrange ( 0 , len ( self . arr ) ) NEW_LINE return self . arr [ index ] NEW_LINE DEDENT def search ( self , x ) : NEW_LINE INDENT return self . hashd . get ( x , None ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT ds = MyDS ( ) NEW_LINE ds . add ( 10 ) NEW_LINE ds . add ( 20 ) NEW_LINE ds . add ( 30 ) NEW_LINE ds . add ( 40 ) NEW_LINE print ( ds . search ( 30 ) ) NEW_LINE ds . remove ( 20 ) NEW_LINE ds . add ( 50 ) NEW_LINE print ( ds . search ( 50 ) ) NEW_LINE print ( ds . getRandom ( ) ) NEW_LINE DEDENT