Randomized set and randomized collection are 2 very similar data structure, which provide 3 methods: insert, delete and getRandom. You can get the details from leetcode Insert Delete GetRandom O(1) and Insert Delete GetRandom O(1) - Duplicates allowed.

It's not hard to implement them. The hard part is how to implement them in O(1) time complexity. Let's see them one by one.

RandomizedSet

The first solution comes to mind for me is to just use a set. But the problem is, with set we can't get a random value from it with O(1) time complexity. We need to convert the set into an array, then we can random index a value from the array.

So the idea to solve this problem is to use both idea. First we use an array to store all the data. So we can randomly choose one element by its index later. Second, we use a hashtable to map values with its index.

The hard part may be the remove operation. Remove value from the map is O(1), but how can we remove a value from the array with O(1) complexity? So the trick is, we put the last element of the array into the index of the element which should be removed. Then pop out the last value. In this way, its just a pop operation, we don't need to iterate all the values in the array, so we have O(1) complexity.

class RandomizedSet {
    private m: Map<number, number>;
    private arr: number[];

    constructor() {
        this.m = new Map();
        this.arr = [];
    }

    insert(val: number): boolean {
        if (this.m.has(val)) {
            return false;
        } else {
            this.arr.push(val);
            this.m.set(val, this.arr.length - 1);
            return true;
        }
    }

    remove(val: number): boolean {
        if (this.m.has(val)) {
            const index = this.m.get(val) as number;
            this.m.delete(val);
            this.arr[index] = this.arr[this.arr.length - 1];
            this.arr.pop();
            this.m.set(this.arr[index], index);
            return true;
        } else {
            return false;
        }
    }

    getRandom(): number {
        return this.arr[Math.floor(Math.random() * this.arr.length)];
    }
}

RandomizedCollection

This data structure add suuport for duplicate element for the randomized set data structure. Even if it is a leetcode hard problem, it's actually not so hard.

We still need to use an array to store all element, so we can randomly choose one later. We still need a hashtable to map element values to its index. But this time, because the value can be duplicated, so the value of the map should be a set of element index.

The hard part is still about the remove operation. We still need to use the trick of popping out later element. But apart from that, we need to figure out how to remove an element from set data structure. In JavaScript, there is no such api for this operation, but we can make use of iterator to achieve that. Specifically, since the iterator executes lazily, so if we only call it once, then we can have O(1) time complexity.

class RandomizedCollection {
    private m: Map<number, Set<number>> = new Map();
    private arr: number[] = [];

    constructor() { }

    insert(val: number): boolean {
        let indexSet = this.m.get(val);
        this.arr.push(val);

        if (indexSet === undefined) {
            indexSet = new Set([this.arr.length - 1]);
            this.m.set(val, indexSet);
        } else {
            indexSet.add(this.arr.length - 1);
        }
        return indexSet.size === 1;
    }

    remove(val: number): boolean {
        let indexSet = this.m.get(val);
        if (indexSet === undefined || indexSet.size === 0) {
            return false;
        } else {
            const removeIndex = indexSet.values().next().value as number;
            indexSet.delete(removeIndex);

            const lastIndex = this.arr.length - 1;
            const lastVal = this.arr[lastIndex];

            this.arr[removeIndex] = lastVal;
            this.arr.pop();

            (this.m.get(lastVal) as Set<number>)
                .add(removeIndex)
                .delete(lastIndex);

            return true;
        }
    }

    getRandom(): number {
        return this.arr[Math.floor(Math.random() * this.arr.length)];
    }
}