Your question is Insert Delete GetRandom in O(1). Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
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.
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.
def randomized_set(operations, seed):