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 have O(1) time complexity
• No duplicate values are allowed in the data structure

When you finish creating DS, here’s an example of what it could look like to use it:

/* Create a new DS object */
let newDS = new DS();
/* Attempt to remove 12 but nothing happens since DS is empty */
newDS.remove(12);
/* Insert 1, 9, 50, 10, and 12 */
newDS.insert(1);
newDS.insert(9);
newDS.insert(50);
newDS.insert(10);
newDS.insert(12);
/* Attempt to insert 1 but nothing happens since it exists */
newDS.insert(1);
/* Attempt to remove 2 but it doesn't exist so nothing happens */
newDS.remove(2);
/* Remove 1 and 12 */
newDS.remove(1);
newDS.remove(12);
/* Get a random number that is in newDS */
const randomNum = newDS.getRandom();
console.log(randomNum);