Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Elixir: Real-World Examples

DIY: Insert Delete GetRandom O(1) - Duplicates Allowed

Explore how to design a data structure supporting insertion, deletion, and random retrieval of elements efficiently, even when duplicates exist. Understand the implementation constraints and gain skills to solve Amazon-style coding challenges.

We'll cover the following...

Problem statement

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

The obj parameter being passed as an argument in the insert(), remove() ,and get_random() methods refers to the struct object.

  • insert(obj, 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(obj, 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.
  • get_random(obj): This function should return a random element from the set in constant time.

Note: Your implementation should aim for constant ...