FastPrepVersioned Key-Value Store with Suffix Truncation
Problem · Design

Versioned Key-Value Store with Suffix Truncation

Learn this problem
● MediumNuro logoNuroFULLTIMEONSITE INTERVIEW

Problem statement

Process an ordered array operations for a versioned key-value store. Each row has one of these forms:

  • ["PUT", key, version, value]: store value for key at version. Replace the value when that exact key and version already exists.
  • ["GET", key, version]: return the value at the greatest stored version less than or equal to version, or "null" when no such version exists.
  • ["DELETE", key, version]: remove every stored value for key whose version is greater than or equal to version.

Return one string per operation in input order. PUT and DELETE return "null"; GET returns its selected value or "null".

The operation order is one committed linearization order. Each operation must observe every earlier operation in the array.

Function

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

Examples

Example 1

operations = [["PUT","a","1","red"],["PUT","a","4","blue"],["GET","a","3"],["GET","a","4"],["DELETE","a","3"],["GET","a","10"],["PUT","a","1","green"],["GET","a","1"]]return = ["null","null","red","blue","null","red","null","green"]

The first read uses version 1, and the second uses exact version 4. Deleting at 3 removes version 4 but preserves version 1. The later put replaces that exact version.

Example 2

operations = [["PUT","x","2","x2"],["PUT","x","5","x5"],["PUT","y","3","y3"],["GET","x","1"],["GET","x","4"],["DELETE","x","2"],["GET","x","9"],["GET","y","3"]]return = ["null","null","null","null","x2","null","null","y3"]

Keys have independent histories. The delete removes both versions of x while leaving y unchanged.

Constraints

  • 1 <= operations.length <= 100000.
  • Every row is exactly one valid PUT, GET, or DELETE form.
  • Every key and value is a non-empty string of at most 100 characters.
  • Every version is a base-10 integer string in the range [0, 1000000000].
  • The total number of characters across all rows is at most 2000000.

More Nuro problems

drafts saved locally
public String[] processVersionedStore(String[][] operations) {
    // Write your solution here.
}
operations[["PUT","a","1","red"],["PUT","a","4","blue"],["GET","a","3"],["GET","a","4"],["DELETE","a","3"],["GET","a","10"],["PUT","a","1","green"],["GET","a","1"]]
expected["null", "null", "red", "blue", "null", "red", "null", "green"]
checking account