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];
}
}
