FastPrepMap with Constant-Time Put All

Map with Constant-Time Put All

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Process an ordered sequence of operations against an initially empty map from string keys to integer values.

  • PUT key value inserts or replaces one key.
  • GET key returns the key's current value, or NULL when the key is absent.
  • PUT_ALL value changes the value of every key currently stored in the map.

The latest applicable PUT or PUT_ALL determines each key's value. A key inserted after a PUT_ALL keeps its newly inserted value until a later operation changes it.

Return one string for every GET operation, in query order. Design PUT_ALL to run in O(1) time.

Function

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

Examples

Example 1

operations = [["PUT","a","1"],["PUT","b","2"],["PUT_ALL","5"],["GET","a"],["PUT","b","7"],["GET","a"],["GET","b"],["GET","c"]]return = ["5","5","7","NULL"]

The bulk assignment sets both existing keys to 5. The later PUT b 7 changes only b, and c is absent.

Example 2

operations = [["PUT_ALL","9"],["PUT","x","3"],["GET","x"],["PUT_ALL","4"],["GET","x"]]return = ["3","4"]

The first bulk assignment affects no keys. Key x is inserted afterward with value 3, then the second bulk assignment changes it to 4.

Constraints

  • 1 <= operations.length <= 100000.
  • Each operation is exactly one of PUT, GET, or PUT_ALL with the required operands.
  • Keys contain lowercase English letters and have length from 1 through 20.
  • Values fit in a signed 32-bit integer.

More Google problems

See Google hiring insights
public String[] processMapOperations(String[][] operations) {
    // Write your code here.
}
operations[["PUT","a","1"],["PUT","b","2"],["PUT_ALL","5"],["GET","a"],["PUT","b","7"],["GET","a"],["GET","b"],["GET","c"]]
expected["5", "5", "7", "NULL"]
Checking account…