Loading problem…
Implement the RandomizedSet class supporting average O(1) time for each operation: RandomizedSet() initializes the object; insert(val) inserts val if not present and returns true, otherwise returns false; remove(val) removes val if present and returns true, otherwise returns false; getRandom() returns a random element from the current set (each element equally likely). At least one element exists when getRandom is called. Note: in this catalog the getRandom calls are set up so exactly one element is present, making the expected output deterministic.
Example 1
Input: operations = ["RandomizedSet","insert","getRandom","remove","insert","getRandom"], arguments = [[],[1],[],[1],[2],[]]
Output: [null,true,1,true,true,2]
Explanation: getRandom is queried only when a single element remains, so its result is deterministic.
Example 2
Input: operations = ["RandomizedSet","insert","insert","remove","getRandom"], arguments = [[],[5],[7],[5],[]]
Output: [null,true,true,true,7]
Explanation: 5 and 7 are inserted, then 5 is removed. Only 7 remains, so getRandom() must return 7.
Example 3
Input: operations = ["RandomizedSet","remove","insert","getRandom"], arguments = [[],[0],[0],[]]
Output: [null,false,true,0]
Explanation: Removing an absent value returns false.
getRandom needs O(1) random access, which points to a plain array (pick a random index). insert needs O(1), which an array append gives. The hard part is remove in O(1): deleting from the middle of an array is normally O(n) because of the shift. The trick is to never delete from the middle — swap the target with the last element, then pop the end. A hash map from value to its current index tells us where the target sits so the swap is O(1).
Run checks all cases above. Submit evaluates all test cases.