Design a data structure that supports insert , delete , search and getRandom in constant time | Java program to design a data structure that support following operations in Theta ( n ) time a ) Insert b ) Delete c ) Search d ) getRandom ; class to represent the required data structure ; Constructor ( creates arr [ ] and hash ) ; A resizable array ; A hash where keys are array elements and values are indexes in arr [ ] ; A Theta ( 1 ) function to add an element to MyDS data structure ; If element is already present , then nothing to do ; Else put element at the end of arr [ ] ; And put in hash also ; 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 remove from arr [ ] 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 Choose a different seed ; Return element at randomly picked index ; Returns index of element if element is present , otherwise null ; Driver class
import java . util . * ; class MyDS { public MyDS ( ) { arr = new ArrayList < Integer > ( ) ; hash = new HashMap < Integer , Integer > ( ) ; } ArrayList < Integer > arr ; HashMap < Integer , Integer > hash ; void add ( int x ) { if ( hash . get ( x ) != null ) return ; int s = arr . size ( ) ; arr . add ( x ) ; hash . put ( x , s ) ; } void remove ( int x ) { Integer index = hash . get ( x ) ; if ( index == null ) return ; hash . remove ( x ) ; int size = arr . size ( ) ; Integer last = arr . get ( size - 1 ) ; Collections . swap ( arr , index , size - 1 ) ; arr . remove ( size - 1 ) ; hash . put ( last , index ) ; } int getRandom ( ) { Random rand = new Random ( ) ; int index = rand . nextInt ( arr . size ( ) ) ; return arr . get ( index ) ; } Integer search ( int x ) { return hash . get ( x ) ; } } class Main { public static void main ( String [ ] args ) { MyDS ds = new MyDS ( ) ; ds . add ( 10 ) ; ds . add ( 20 ) ; ds . add ( 30 ) ; ds . add ( 40 ) ; System . out . println ( ds . search ( 30 ) ) ; ds . remove ( 20 ) ; ds . add ( 50 ) ; System . out . println ( ds . search ( 50 ) ) ; System . out . println ( ds . getRandom ( ) ) ; } }