Data Structure which support Insert delete, Random in O(1) time


Asked In: FlipkartGoogleMicrosoft

Design a data structure that supports all following operations in O(1) Time insert(Num): Inserts a Num to the set if not already present. remove(Num): Removes a Num from the set if present. getRandom: Returns a random element from current set of elements

Example:

Set set = new Set();
// Inserts 5 to the set. Returns true as 5 was inserted successfully.
set.insert(5); – O(1) Time
// Inserts 6 to the set, returns true. Set now contains [5,6].
set.insert(6);
// getRandom should return either 5 or 6 randomly.
randomSet.getRandom(); – O(1) Time
// Removes 5 from the set, returns true. Set now contains [6].
randomSet.remove(5); – O(1) Time

Hint1: For Finding Random Number Module operator with the size of the set
Hint2: Hashmap takes O(1) time in Get() and Put() Operation

Problem level: Medium