Photo by Alexandru Acea

Deep Dive: Let’s create a data structure that handles insert, delete, and getRandom in O(1) time, no duplicates allowed

A coding problem and solution, explained with JavaScript.

Familiar with common data structures in computer science? If so, you’re probably aware that there are pros and cons to any data structure. In this article I’ll describe and solve a particular coding problem that helps demonstrate data structure tradeoffs by way of example. Let’s go over the problem!

Diving into the problem

The task here is to design our very own data structure (a class) named DS. It should have the following methods:

• An insert function for adding new values to the data structure. It receives one value and returns either true or false to indicate if insertion happened or not.
• A delete function for removing values from the data structure. It receives one value and returns either true or false to indicate if deletion happened or not.
• A getRandom function that returns a random value from the data structure. If the data structure has no entries then it should just return false.

Additionally, DS must follow these two guidelines:

• All functions must…