DIY: Insert, Delete, and GetRandom in O(1)

Solve the interview question "Insert, Delete, and GetRandom in O(1)" yourself in this lesson.

We'll cover the following

Problem statement

Implement a set data structure that can perform the following operations:

  • insert(data): This function should insert data into the set (if the set does not contain it already). It should return false if the data already exists in the set. Otherwise, it should return true.
  • remove(data): If the data is present, this function should remove data from the set and return true. If the data does not exist in the set, the function should return false.
  • getRandomData(): This function should return a random element from the set in constant time.

Note: Your implementation should aim for constant running time (on average) for each operation.


The inputs to the insert() and remove() functions will be integers. The getRandomData() function will have no input.



The outputs of the insert() and remove() functions will be Booleans. While the getRandomData() function will return an integer. The following is an example output that corresponds to the input given above:


Level up your interview prep. Join Educative to access 80+ hands-on prep courses.