Versioned Key-Value Store
Asked at Snowflake· Screen
Reported by the problem's creator, not verified
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.
Examples
Example 1
Input: 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"]Explanation: 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
Input: init =
[], operations =[["put",["k",""]],["get",["k"]]]Output:
[1,""]Explanation: 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.