Insert Delete GetRandom O(1)
Design a collection of distinct integers that supports adding, removing and picking a uniformly random member, each in O(1) average time.
Implement the class RandomizedSet:
new RandomizedSet()creates an empty set.insert(val)addsvalif it is not there and returnstrue; if it was already there it returnsfalse.remove(val)removesvaland returnstrue; if it was not there it returnsfalse.getRandom()returns one current member, chosen so that every member is equally likely. It is only called when the set is not empty.
Because getRandom is random, a test can only check it when the answer is forced. When the set holds exactly one value, the expected output is that value; when it holds several, the output is null and isn't checked. Your code still has to return a valid member.
Each test is a sequence of calls. The first call creates the object.
Constraints
-2^31 <= val <= 2^31 - 1- At most
2 * 10^5calls in total.
Examples
Example 1
Input: ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
Output: [null,true,false,true,null,true,false,2]remove(2) fails because 2 is not in yet. After insert(2) and remove(1) only 2 remains, so getRandom must return 2. When several values are stored the test cannot check which one you return.
Example 2
Input: ["RandomizedSet","insert","insert","remove","remove","insert","getRandom"]
[[],[5],[5],[5],[5],[7],[]]
Output: [null,true,false,true,false,true,7]Inserting a duplicate and removing a missing value both return false.
Example 3
Input: ["RandomizedSet","remove","insert","getRandom","remove","insert"]
[[],[0],[0],[],[0],[0]]
Output: [null,false,true,0,true,true]Zero is a perfectly good member; do not treat a falsy index or value as missing.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Map and Set Arrays: create, read, update
class RandomizedSet {
constructor() {
}
/**
* @param {number} val
* @return {boolean} true if the value was added, false if it was already present
*/
insert(val) {
}
/**
* @param {number} val
* @return {boolean} true if the value was removed, false if it was not present
*/
remove(val) {
}
/** @return {number} a random member, every member equally likely */
getRandom() {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.