You are to build a simple key-value store for storing integers (keys are strings, values are integers) and a global version number (integer).
You will not persist data to disk. You will store the data in memory.
The global version number is an integer that increases monotonically. Every time any key is written with a value, the global version number is increased. The first write has global version number 1, the second write has global version number 2, and so on.
The store supports three operations:
PUT <key> <value>
Set the key name to the value. Key strings will not contain spaces.
Print out the version number, the key, and the value as:PUT(#version number) <key> = <value>GET <key>
Print out the key and the last value of the key, or<NULL>if that key has never been set:GET <key> = <value>GET <key> <version number>
Print out the key, the version number, and the value of the key as it was at the time of the version number, or<NULL>if that key was not set at that time:GET <key>(#version number) = <value>
If the version number has not yet been recorded, return the most recent value for the key.
See below for examples of formatted output for each input.
This problem asks you to design an in-memory key-value store that supports both latest-value lookup and historical lookup by version. A typical solution keeps, for each key, a versioned history of values in increasing version order. PUT increments the global version and appends the new value for that key, while GET <key> returns the most recent value and GET <key> <version> finds the value active at that version, usually with binary search over the stored history. The main challenge is handling versioned queries efficiently without persisting data to disk.
