Multiset

Problem

Design a multiset with random function that will give a random element from the multiset.
The probability to get the number should be linearly proportial to the frequency of occurence of that number in the multiset.

Time Complexity

• insert:
  • Worst Case: $$O(log n)$$
  • Average: $$O(1)$$
• remove
  • Worst Case: $$O(log n)$$
  • Average: $$O(1)$$
• getRandom
  • Worst Case: $$O(n)$$

Code

Approach 1

var RandomizedCollection = function () {
  this.multiset = new Map();
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function (val) {
  if (this.multiset.has(val)) {
    let count = this.multiset.get(val);
    this.multiset.set(val, count + 1);
    return false;
  }
  this.multiset.set(val, 1);
  return true;
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function (val) {
  if (this.multiset.has(val)) {
    let newCount = this.multiset.get(val) - 1;

    if (newCount == 0) {
      this.multiset.delete(val);
    } else {
      this.multiset.set(val, newCount);
    }
    return true;
  }
  return false;
};

/**
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function () {
  let total = 0;

  let nums = [];

  for (let [_, count] of this.multiset) {
    total += count;
  }
  let rand = Math.floor(Math.random() * total * 10) % total;

  // Now determine where the rand will fall in the map

  let passed = 0;

  console.log(this.multiset);

  for (let [value, count] of this.multiset) {
    passed += count;

    if (passed >= rand) {
      console.log(rand, "Found at", value);
      return value;
    }
  }

  return 0;
};

let r = new RandomizedCollection(0);
console.log(r.insert(1));
console.log(r.insert(2));
console.log(r.insert(2));
console.log(r.insert(3));
console.log(r.getRandom());

Approach 2

class Multiset {
  multiset: Map<number, Set<number>>;
  list: number[];

  constructor() {
    this.list = new Array();
    this.multiset = new Map<number, Set<number>>();
  }

  // inserts and returns true if val is inserted for the first time
  insert(val: number): boolean {
    let position = this.list.length;
    this.list.push(val);

    let indices = this.multiset.get(val);

    // this is the first time val is inserted
    if (indices == undefined) {
      this.multiset.set(val, new Set([position]));
      return true;
    }

    // val is already present in multiset
    let size = indices.size;
    indices.add(position);

    if (size == 0) {
      return true;
    }
    return false;
  }

  // removes and returns true if val was present in multiset
  remove(val: number): boolean {
    if (this.list.length == 0) return false;

    let indices = this.multiset.get(val);
    if (indices == undefined) return false;

    if (indices.size == 0) return false;

    let valIndices = Array.from(indices);

    // val is preset at valIndex in this.list
    let valIndex = valIndices.pop();

    // this should never happen as we maintain the invariant that indices.size > 0
    if (valIndex == undefined) return false;

    let lastValueIndex = this.list.length - 1;
    let lastValue = this.list.pop() as number;

    // the number we are trying to remove is also the number at the end of the list
    if (lastValue != val) {
      this.list[valIndex] = lastValue;
    }

    // move the lastValue to valIndex in list and set
    this.multiset.get(lastValue)?.delete(lastValueIndex);
    // neet to sort them as JS set are not sorted
    let finalIndices = Array.from(this.multiset.get(lastValue) as Set<number>);
    finalIndices.sort();
    this.multiset.set(lastValue, new Set(finalIndices));

    indices.delete(valIndex); // remove the valIndex from set

    return true;
  }

  getRandom(): number {
    let n = this.list.length;
    let randomIndex = Math.floor(Math.random() * 10 * n) % n;
    return this.list[randomIndex];
  }
}