FastPrepSparse Set with Constant-Time Updates

Sparse Set with Constant-Time Updates

Google logoGoogle● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

Maintain a set of integers in [0,maxValue] using a dense array and a sparse position array.

  • [0,value] adds value; adding an existing value changes nothing.
  • [1,value] removes value; removing a missing value changes nothing.
  • [2,value] queries membership and produces one Boolean output.

Every operation must run in worst-case O(1) time. Return query results in operation order.

Function

processSparseSet(maxValue: int, operations: int[][]) → boolean[]

Examples

Example 1

maxValue = 10operations = [[0,3],[0,7],[2,3],[1,3],[2,3],[2,7]]return = [true,false,true]

Three and seven are added; removing three does not affect seven.

Example 2

maxValue = 2operations = [[0,1],[0,1],[2,1],[1,1],[1,1],[2,1]]return = [true,false]

Duplicate add and remove operations are idempotent.

Example 3

maxValue = 0operations = []return = []

No operations produce no query results.

Constraints

  • 0 <= maxValue <= 1000000.
  • 0 <= operations.length <= 200000.
  • Every operation has exactly two integers and a value in [0,maxValue].
  • Operation type is 0, 1, or 2.

More Google problems

See Google hiring insights
public boolean[] processSparseSet(int maxValue, int[][] operations) {
    // Write your code here.
}
maxValue10
operations[[0,3],[0,7],[2,3],[1,3],[2,3],[2,7]]
expected[true,false,true]
Checking account…