Randomized Set Implementation

EasyPython

Problem

Hive's activity systems need a collection that stores unique integer identifiers and supports fast updates and random selection. Implement a randomized_set function that processes operations using a data structure with average O(1) time for insertion, removal, and random selection.

Formal Specification

The function receives operations, a list of operation arrays. Each operation is one of:

["insert", value]: Add value if it is absent. Return true if inserted, otherwise false.
["remove", value]: Remove value if present. Return true if removed, otherwise false.
["getRandom"]: Return one uniformly random value currently stored. This operation is called only when the set is non-empty.

Return a list containing the result of every operation, in order. The implementation may use Python's random module. The required data structure should use an array for indexed random access and a hash map for locating values during removal.

Constraints

1 <= operations.length <= 2 * 10^5
Values are integers in [-10^9, 10^9]
getRandom is called only when the set is non-empty
Values must be unique in the set
getRandom must select each stored value with equal probability

Function Signature

def randomized_set(operations):

Formal Specification

The function receives operations, a list of operation arrays. Each operation is one of:

["insert", value]: Add value if it is absent. Return true if inserted, otherwise false.
["remove", value]: Remove value if present. Return true if removed, otherwise false.
["getRandom"]: Return one uniformly random value currently stored. This operation is called only when the set is non-empty.