JSFiddle - React, Tailwind, and code Playground

by asdf

JavaScript

// Design a data structure that supports insert, delete, search and getRandom in constant time

function ConstantTimeStructure() {
	this.arr = [];
	this.map = {};
}
ConstantTimeStructure.prototype.insert = function (item) {
	if (this.map.hasOwnProperty(item)) {
  	return;  	
  } 
	var idx = this.arr.length;
	this.arr.push(item);
  this.map[item] = idx;
};
ConstantTimeStructure.prototype.delete = function (item) {
  var idx, lastItem;
  if (this.map.hasOwnProperty(item)) {
  	idx = this.map[item];
    lastItem = this.arr.pop();
    if (item === lastItem) {
    	return;
    }
   	this.arr[idx] = lastItem;
    this.map[lastItem] = idx;
    delete this.map[item];
  }
};
ConstantTimeStructure.prototype.search = function (item) {
  if (this.map.hasOwnProperty(item)) {
  	return true;  	
  } 
  return false;
};
ConstantTimeStructure.prototype.getRandom = function () {
  var random = Math.floor(Math.random() * (this.arr.length - 0));
  return this.arr[random];
};

var structure = new ConstantTimeStructure();

console.log(structure.getRandom());
console.log(structure.search(1));
structure.delete(1);
console.log(structure.arr, structure.map);
console.log('============================');
structure.insert(1);
structure.insert(1);
structure.insert(2);
console.log(structure.getRandom());
console.log(structure.search(1));
console.log(structure.arr, structure.map);
structure.delete(1);
console.log(structure.arr, structure.map);
structure.delete(2);
console.log(structure.arr, structure.map);