Versioned Key-Value Store

SnowflakePhone screenMedium

Design a versioned string store. A single counter numbers every change to the store across all keys: the first change is version 1, the next is version 2, and so on. Keys and values are strings; a value may be the empty string.

Each test drives one VersionedStore() instance through a sequence of calls and checks every return value. Each example below drives one instance: init holds the constructor arguments and operations is a list of [method, [args]] calls; the output lists every call's return value.

Part 1: Versioned reads

Implement a store with:

put(key, value) stores value under key as a new change and returns its version number.
get(key, version=-1) returns the value key held right after version: the value from its newest put with a version at most version. A version of -1, or one beyond the latest, means the latest state.

Return None if the key had no value at that point, including version = 0.

Example 1

init: []
operations: [["put",["k","a"]],["put",["k","b"]],["put",["j","x"]],["put",["k","c"]],["get",["k"]],["get",["k",1]],["get",["k",2]],["get",["k",3]],["get",["k",4]],["get",["j"]],["get",["j",2]],["get",["j",3]],["get",["zz"]],["get",["k",0]],["get",["k",99]],["get",["k",-1]]]
Output: [1,2,3,4,"c","a","b","b","c","x",null,"x",null,null,"c","c"]

Why: Versions: k=a is 1, k=b is 2, j=x is 3, k=c is 4. get(k,3) is still b because the third put touched another key. get(j,2) is None because j did not exist yet. Version 0 gives None, an unknown key gives None, and version 99 behaves as latest.

Example 2
init
[]
operations
[["put",["k",""]],["get",["k"]]]
Output
[1,""]
Why: put("k", "") stores the empty string as version 1 and returns 1. get("k") then returns "" because the empty string is a real stored value, not a missing key.

Constraints

1 <= len(operations) <= 10^4
1 <= len(key) <= 10
0 <= len(value) <= 10
version = -1 or 0 <= version <= 10^5