Constant-Time Randomized Set | Dataford Interview Questions

Your question is Constant-Time Randomized Set. 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.

Problem

Match Group services need a lightweight set of active profile identifiers that supports fast updates and random profile selection. Implement randomized_set(operations, seed) so every insert, delete, and getRandom operation runs in average O(1) time.

Formal Specification

operations is a list of two-element lists: [operation, value] for insert and delete, or ['getRandom', null] for random selection.
operation is one of 'insert', 'delete', or 'getRandom'.
value is an integer when required and null for getRandom.
Return a list containing one result per operation. insert and delete return booleans. getRandom returns one currently stored integer.
Use seed to make random selections reproducible during testing. The returned value must be uniformly selected from the current set.
The input never calls getRandom when the set is empty.

Constraints

1 <= operations.length <= 2 * 10^5
-10^9 <= value <= 10^9
Values are integers.
The set contains no duplicate values.
getRandom is never called when the set is empty.
seed is an integer.

Function Signature

def randomized_set(operations, seed):

Your question is Constant-Time Randomized Set. 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.

Formal Specification

operations is a list of two-element lists: [operation, value] for insert and delete, or ['getRandom', null] for random selection.
operation is one of 'insert', 'delete', or 'getRandom'.
value is an integer when required and null for getRandom.
Return a list containing one result per operation. insert and delete return booleans. getRandom returns one currently stored integer.
Use seed to make random selections reproducible during testing. The returned value must be uniformly selected from the current set.
The input never calls getRandom when the set is empty.

Constraints

1 <= operations.length <= 2 * 10^5
-10^9 <= value <= 10^9
Values are integers.
The set contains no duplicate values.
getRandom is never called when the set is empty.
seed is an integer.

Function Signature

def randomized_set(operations, seed):