Data structure in JavaScript that supports Insert, Remove and GetRandomElement

Question

I stumbled upon this interview question and I wanted to find a solution for it in JavaScript (rather than Java or C++):

Implement a set-like data structure that supports Insert, Remove, and GetRandomElement efficiently. Example: If you insert the elements 1, 3, 6, 8 and remove 6, the structure should contain [1, 3, 8]. Now, GetRandom should return one of 1, 3 or 8 with equal probability.

This is answered in Java here: Data structure: insert, remove, contains, get random element, all at O(1) However, it doesn't offer example code. I am a beginner and am just learning how to use hash tables so if you can give an explanation of the code, I would appreciate that!

javascript has a data structure for [sets in ES6](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set), other than that you can use an array. A hash table should correspond to an object or map and I don't think it's fit for the job — maioman, Jan 05 '17 at 20:41

Abhineet Kandele · Answer 1 · 2020-06-13T18:21:50.707

Here are two of the simple solutions:

First:

var RandomizedSet = function() {
    this.values = [];
};

RandomizedSet.prototype.insert = function(val) {
    if (this.values.includes(val)) return false;
    this.values.push(val);
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    const idx = this.values.indexOf(val);
    if (idx === -1) return false;
    this.values.splice(idx,1);
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    return this.values[Math.floor(Math.random() * this.values.length)]  ;
};

Second:

var RandomizedSet = function() {
    this.values = {};
    this.length = 0;
};

RandomizedSet.prototype.insert = function(val) {
    if (this.values[val] !== null && this.values[val] !== undefined) return false;
    this.values[val] = val;
    this.length++;
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    if (this.values[val] === null || this.values[val] === undefined) return false;
    delete this.values[val];
    this.length--;
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    return Object.keys(this.values)[Math.floor(Math.random() * this.length)]  ;
};

Nice. You may improve this by using Stack Overflow's embedded code snipet. You should be able to provide calls to these functions to show examples. Also compare time complexities of each of the functions in both versions. — Rahul Bhobe, Jun 13 '20 at 18:40

score 1 · Answer 2 · answered Jan 05 '17 at 20:44

You could use a JavaScript object.

Create an object: var testObject = {};

Insert key/value pair

testObject["keyName"] = "value here"; or testObject.keyName = "value here";

Delete key

delete testObject["keyName"];

Get Random

function pickRandomProperty(object) {
 var keys = Object.keys(object);

 if(keys.length > 0){
    return keys[Math.floor(keys.length * Math.random())];
 }
 else{
    return false;
 }
}

This will return a random key in which you can then use to get the value: testObject[randomKey]

score 0 · Answer 3 · edited May 23 '17 at 11:53

Let's suppose we have these assumptions:

Object.keys has not a constant complexity.
Have a constant complexity: array.pop(), object[key], delete object[key], Math.floor(n)

One solution is to keep track of all elements in an array and their indexes in an object. By doing this, we can remove an element by swapping it and the last, then use the pop function, by supposing it has a constant comlexity.

'use strict'

function SetStructure () {
  this._length = 0
  this._obj = {}
  this._arr = []
}

SetStructure.prototype.remove = function (el) {
  const idx = this._obj[el]
  if (typeof idx !== 'number') {
    return false
  }
  delete this._obj[el]
  this._arr[idx] = this._arr[this._length-1]
  this._length--
  this._arr.pop()
  return true
}

SetStructure.prototype.insert = function (el) {
  const idx = this._obj[el]
  if (typeof idx === 'number') {
    return false
  }
  this._obj[el] = this._length++
  this._arr.push(el)
  return true
}

SetStructure.prototype.getRandom = function () {
  return this._arr[Math.floor(Math.random() * this._length)]
}


let s = new SetStructure()
s.insert(1)
s.insert(3)
s.insert(6)
s.insert(8)
s.remove(6)

score 0 · Answer 4 · answered Jan 05 '17 at 22:04

I ended up doing this by creating a set data structure:

function Set() {

    let items = {};

    this.add = function(value) {
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };

    this.delete = function(value) {
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };

    this.has = function(value) {
        return items.hasOwnProperty(value);
    };

    this.values = function() {
        let values = [];
        for (let i = 0, keys = Object.keys(items); i < keys.length; i++) {
            values.push(items[keys[i]]);
        }
        return values;
    };

    this.getRandomElement = function() {
        var keys = Object.keys(items);
        return items[keys[Math.floor(Math.random() * keys.length)]];
    };
}

Tested it accordingly:

let set = new Set();

set.add(1);
set.add(3);
set.add(6);
set.add(8);
console.log(set.values()); 
    // [1, 3, 6, 8];
set.delete(6);
console.log(set.values()); 
    // [1, 3, 8];
console.log(set.getRandomElement());

Data structure in JavaScript that supports Insert, Remove and GetRandomElement

4 Answers4