Data Structure – Design a data structure which performs in Big (O) Constant time

Design a data structure which performs the following operations in O(1) time complexity.

Insert
Remove
Search
Find Random element from the current set of elements (This is the tricky part) based on the size of the data structure

Info: Assume all data stored with the structure is Integer.

To solve this problem efficiently there are couple of things one should be familiar with

Analyzing time complexity (Big O notation)
Stack Data Structure
Array Data Structure
Hash/Hashmap/Dictionary data structure

Let’s consider consider stack, hashmap and array for this and let’s see which one or which combinations can give at the desired result. Let’s begin with stack.

HINT: You can use the random generator available in your programming language that gives your the value between 0 and length-1 of the data structure in almost equal probability.

Assume we have the following data inserted into our data structure

10, 15, 30, 25, 20, 40

Stack

✅Insert (push) can be done in O(1)
✅Delete (pop) can be done in O(1)
❌Search will need O(N) as all elements has to be traversed.
❌Finding random element cannot be achieved in O(1) (as search itself take O(N) time)

Now, as it is clear from the above observation stack is not suitable for this specific scenario, let’s head over to hash/hashmap data structure.

Hash/HashMap/Dictionary

✅Insert (put) can be done in O(1)
✅Delete (remove) can be done in O(1)
✅Search we can do in O(1) using search by key
❌Finding Random element cannot be done in O(1)

In Hash like structure finding random element is difficult or a complex operations.

Array

✅ Insert (push) can be done in O(1)
✅ Delete (remove) can be done in O(1)
❌Search we can do in O(N) as all element has to be traversed
✅ Finding Random element can be done in O(1)

Solution

We will use Array and Hash together to solve this problem. So, we have the below data to be inserted into our new data structure.

10, 15, 30, 25, 20, 40

We will call our new data structure as HashList.

Steps to perform when adding data

Add every element to the array (or ArrayList depending on the language you use)
The array value will become the key and the array index will become the hash’s value.

For e.g after adding the above numbers our data structure will visually look like below figure.

For deleting items, we have to account for gaps in the data.

The source code in JavaScript is given below. I haven’t done error handling and other things which is not part of the core solution.

class HashList {
  constructor() {
    this.arr = [];
    this.map = {};
  }
  
  insert(data) {
    // if num already added, then skip
    if (this.map[data]) return;
    
    let size  = this.arr.length;
    
    // Add the 'num' as value to array
    this.arr.push(data);
    
    // Add the array index as value to map 
    // and the 'num'being index
    this.map[data] = size;
  }
  
  delete(data) {
    // Get the key from the map
    let index = this.map[data];
    console.log(index);
    
    // Remove the element from the map
    delete this.map[data];
    
    // STEPS TO REMOVE FROM ARRAY
    // Get the old length
    const size = this.arr.length;
    
    // Get the last index
    const lastElement = this.arr[size-1];
    console.log(`last ele: ${lastElement}`);
    console.log(`ele to remove at index: ${index}`);
    
    
    // Swap the elements index and size-1.  
    // Here we areusing ES6 destructuring.  
    // Alternatively You can also use array splice method

    [this.arr[index], this.arr[size-1]] = 
          [this.arr[size-1], this.arr[index]]
    
    
    // Remove the last element
    this.arr.splice(size-1,1);
    
    // Update the map value
    this.map[lastElement] = index;
  }

  // Get element at random index
  getRandom() {
    let index = Math.floor(Math.random() * this.arr.length);
    console.log(`Random index ${index}`);
    return this.arr[index];
  }
    
  // For debugging purpose
  getArray() {
    return this.arr;
  }
  
  getHash() {
    return this.map;
  }
  
}

//10, 15, 30, 25, 20, 40
const hl = new HashList();
hl.insert(10);
hl.insert(15);
hl.insert(30);
hl.insert(25);
hl.insert(20);
hl.insert(40);

console.log(hl.getArray());
console.log(hl.getHash());

hl.delete(15);
console.log(hl.getArray());
console.log(hl.getHash());

// Random element index
for(let i = 0; i < 5; i++) {
  console.log(hl.getRandom());  
}

The complete source code can be tried out here

https://jsbin.com/qahupos/edit?js,console,output

<Activity for you In case you reached here, please feel free to post your solution/link to solution in the comment section.

(Usually asked in Google, Facebook, Amazon)

#faang #productcompany #facebook #apple #amazon #netflix #google #uber #microsoft #algorisys

Blog