Insert Delete GetRandom in O(1)

MediumPython

Problem

DataVisor's real-time fraud detection pipeline needs a set of active risk signals that supports insertion, removal, and uniformly selecting one signal for evaluation. Implement all operations in average O(1) time.

Create a function that processes a sequence of operations. An insert adds a value only if it is not already present. A remove deletes a value only if it exists. A getRandom operation returns one currently stored value, with every stored value having equal probability. To make evaluation reproducible, the function receives a random seed.

Formal Specification

Implement randomized_set(operations, seed), where operations is a list of two-element lists. The first element is one of "insert", "remove", or "getRandom"; the second element is required for the first two operations and omitted for getRandom. Values are integers. Return a list containing the Boolean result of each insert or remove, and the selected integer for each getRandom.

Use an array for compact storage and a hash map from value to array index. Deletion must not shift remaining elements.

Constraints

1 <= len(operations) <= 10^5
Values are integers in [-10^9, 10^9]
getRandom is called only when the set is non-empty
Duplicate inserts and missing removals are valid operations
Random selection must be uniform over current values

Function Signature

def randomized_set(operations, seed):

Formal Specification

Use an array for compact storage and a hash map from value to array index. Deletion must not shift remaining elements.