How should I practice Constant-Time Set Operations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Pure Storage phone screen problems in FastPrep.

Is Constant-Time Set Operations associated with Pure Storage?

FastPrep tags this as a Pure Storage phone screen coding practice problem when the problem catalog has that company and stage context.

Constant-Time Set Operations

Pure Storage● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

Process a sequence of operations on an integer set. PUT x inserts x only when it is not currently present. GET x appends true or false to the returned array. ITERATE appends one comma-separated string containing the current values in first-insertion order, or an empty string when the set is empty. CLEAR removes every current value. The paired integer is ignored for ITERATE and CLEAR.

Use expected constant time for each PUT, GET, and CLEAR, and constant time to obtain the start of an iteration. Materializing an ITERATE result may take time proportional to the number of emitted values.

Function

processConstantTimeSet(operations: String[], values: int[]) → String[]

Examples

Example 1

operations = ["PUT","PUT","GET","ITERATE"]values = [4,7,4,0]return = ["true","4,7"]

The membership query finds 4, and iteration preserves first-insertion order.

Example 2

operations = ["PUT","CLEAR","GET","PUT","ITERATE"]values = [9,0,9,3,0]return = ["false","3"]

CLEAR invalidates the prior generation in constant time before 3 starts the new insertion order.

Constraints

1 <= operations.length == values.length <= 200000
operations[i] is PUT, GET, ITERATE, or CLEAR
values[i] is a signed 32-bit integer
values[i] is ignored for ITERATE and CLEAR
the total number of values emitted by ITERATE operations is at most 200000