How should I practice Insert, Delete, And Get Random In Constant Time?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs onsite interview problems in FastPrep.

Is Insert, Delete, And Get Random In Constant Time associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Insert, Delete, And Get Random In Constant Time

Learn this problem

● Medium

Goldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

Implement a set of integers that supports each of the following operations in average constant time:

insert x adds x when it is absent and otherwise leaves the set unchanged.
remove x deletes x when it is present and otherwise leaves the set unchanged.
getRandom returns one uniformly random value from the current set.

Process the commands in operations from left to right, starting from an empty set. Append one result for every command:

For insert x, append "true" if x was absent and became inserted, otherwise append "false".
For remove x, append "true" if x was present and became removed, otherwise append "false".
For getRandom, append the unique remaining value as a decimal integer string.

Every getRandom command is issued only when the set currently contains exactly one value, so the judged output is deterministic. Design the structure so that a later getRandom on a larger set would still be average O(1); the tests never ask for a stochastic sample from a multi-value set.

Each command is exactly insert x, remove x, or getRandom, where x is a signed decimal integer.

What the interview report shared

The Superday report asked to design a data structure that can put, delete, and get a random element, each in O(1).

Function

processRandomizedSet(operations: String[]) → String[]

Examples

Example 1

operations = ["insert 1","insert 2","remove 1","getRandom"]return = ["true","true","true","2"]

Inserting 1 and 2 both succeed. Removing 1 leaves only 2, so getRandom must return 2.

Example 2

operations = ["insert 3","remove 4","insert 3","getRandom"]return = ["true","false","false","3"]

The first insert creates singleton 3. Removing missing 4 and inserting 3 again both return false. The set still holds only 3.

Constraints

1 <= operations.length <= 10^5.
Each operation is exactly insert x, remove x, or getRandom.
-10^9 <= x <= 10^9.
Every getRandom occurs only when the set currently has size 1.