Design a data structure that supports following operations in Θ(1) time.
insert(x): Inserts an item x to the data structure if not already present.
remove(x): Removes an item x from the data structure if present.
search(x): Searches an item x in the data structure.
getRandom(): Returns a random element from current set of elements
We can use hashing to support first 3 operations in Θ(1) time. How to do the 4th operation? The idea is to use a resizable array (ArrayList in Java, vector in C) together with hashing. Resizable arrays support insert in Θ(1) amortized time complexity. To implement getRandom(), we can simply pick a random number from 0 to size-1 (size is number of current elements) and return the element at that index. The hash map stores array values as keys and array indexes as values.
Following are detailed operations.
insert(x)
1) Check if x is already present by doing a hash map lookup.
2) If not present, then insert it at the end of the array.
3) Add in hash table also, x is added as key and last array index as index.
remove(x)
1) Check if x is present by doing a hash map lookup.
2) If present, then find its index and remove it from hash map.
3) Swap the last element with this element in array and remove the last element.
Swapping is done because the last element can be removed in O(1) time.
4) Update index of last element in hash map.
getRandom()
1) Generate a random number from 0 to last index.
2) Return the array element at the randomly generated index.
search(x)
Do a lookup for x in hash map.
Below is Java implementation of the data structure.
[pastacode lang=”java” manual=”%2F*%20Java%20program%20to%20design%20a%20data%20structure%20that%20support%20folloiwng%20operations%0A%20%20%20in%20Theta(n)%20time%0A%20%20%20a)%20Insert%0A%20%20%20b)%20Delete%0A%20%20%20c)%20Search%0A%20%20%20d)%20getRandom%20*%2F%0Aimport%20java.util.*%3B%0A%20%0A%2F%2F%20class%20to%20represent%20the%20required%20data%20structure%0Aclass%20MyDS%0A%7B%0A%20%20%20ArrayList%3CInteger%3E%20arr%3B%20%20%20%2F%2F%20A%20resizable%20array%0A%20%0A%20%20%20%2F%2F%20A%20hash%20where%20keys%20are%20array%20elements%20and%20vlaues%20are%0A%20%20%20%2F%2F%20indexes%20in%20arr%5B%5D%0A%20%20%20HashMap%3CInteger%2C%20Integer%3E%20%20hash%3B%0A%20%0A%20%20%20%2F%2F%20Constructor%20(creates%20arr%5B%5D%20and%20hash)%0A%20%20%20public%20MyDS()%0A%20%20%20%7B%0A%20%20%20%20%20%20%20arr%20%3D%20new%20ArrayList%3CInteger%3E()%3B%0A%20%20%20%20%20%20%20hash%20%3D%20new%20HashMap%3CInteger%2C%20Integer%3E()%3B%0A%20%20%20%7D%0A%20%0A%20%20%20%2F%2F%20A%20Theta(1)%20function%20to%20add%20an%20element%20to%20MyDS%0A%20%20%20%2F%2F%20data%20structure%0A%20%20%20void%20add(int%20x)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%20If%20ekement%20is%20already%20present%2C%20then%20noting%20to%20do%0A%20%20%20%20%20%20if%20(hash.get(x)%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20Else%20put%20element%20at%20the%20end%20of%20arr%5B%5D%0A%20%20%20%20%20%20int%20s%20%3D%20arr.size()%3B%0A%20%20%20%20%20%20arr.add(x)%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20And%20put%20in%20hash%20also%0A%20%20%20%20%20%20hash.put(x%2C%20s)%3B%0A%20%20%20%7D%0A%20%0A%20%20%20%2F%2F%20A%20Theta(1)%20function%20to%20remove%20an%20element%20from%20MyDS%0A%20%20%20%2F%2F%20data%20structure%0A%20%20%20void%20remove(int%20x)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Check%20if%20element%20is%20present%0A%20%20%20%20%20%20%20Integer%20index%20%3D%20hash.get(x)%3B%0A%20%20%20%20%20%20%20if%20(index%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20If%20present%2C%20then%20remove%20element%20from%20hash%0A%20%20%20%20%20%20%20hash.remove(x)%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Swap%20element%20with%20last%20element%20so%20that%20remove%20from%0A%20%20%20%20%20%20%20%2F%2F%20arr%5B%5D%20can%20be%20done%20in%20O(1)%20time%0A%20%20%20%20%20%20%20int%20size%20%3D%20arr.size()%3B%0A%20%20%20%20%20%20%20Integer%20last%20%3D%20arr.get(size-1)%3B%0A%20%20%20%20%20%20%20Collections.swap(arr%2C%20index%2C%20%20size-1)%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Remove%20last%20element%20(This%20is%20O(1))%0A%20%20%20%20%20%20%20arr.remove(size-1)%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Update%20hash%20table%20for%20new%20index%20of%20last%20element%0A%20%20%20%20%20%20%20hash.put(last%2C%20index)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Returns%20a%20random%20element%20from%20MyDS%0A%20%20%20%20int%20getRandom()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Find%20a%20random%20index%20from%200%20to%20size%20-%201%0A%20%20%20%20%20%20%20Random%20rand%20%3D%20new%20Random()%3B%20%20%2F%2F%20Choose%20a%20different%20seed%0A%20%20%20%20%20%20%20int%20index%20%3D%20rand.nextInt(arr.size())%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Return%20element%20at%20randomly%20picked%20index%0A%20%20%20%20%20%20%20return%20arr.get(index)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Returns%20index%20of%20element%20if%20element%20is%20present%2C%20otherwise%20null%0A%20%20%20%20Integer%20search(int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20return%20hash.get(x)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20class%0Aclass%20Main%0A%7B%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20MyDS%20ds%20%3D%20new%20MyDS()%3B%0A%20%20%20%20%20%20%20%20ds.add(10)%3B%0A%20%20%20%20%20%20%20%20ds.add(20)%3B%0A%20%20%20%20%20%20%20%20ds.add(30)%3B%0A%20%20%20%20%20%20%20%20ds.add(40)%3B%0A%20%20%20%20%20%20%20%20System.out.println(ds.search(30))%3B%0A%20%20%20%20%20%20%20%20ds.remove(20)%3B%0A%20%20%20%20%20%20%20%20ds.add(50)%3B%0A%20%20%20%20%20%20%20%20System.out.println(ds.search(50))%3B%0A%20%20%20%20%20%20%20%20System.out.println(ds.getRandom())%3B%0A%20%20%20%20%7D%0A%7D” message=”Java Program” highlight=”” provider=”manual”/]Output:
2 3 40