TikTok VO 面试真题解析：Simple Key-Value Store with Versioned Integers

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.

这道题本质上是一个支持“历史版本查询”的内存版 KV Store。普通 GET 只需要记录每个 key 的最新值；而带版本号的 GET 则要求能回看某一时刻该 key 的值，因此通常需要为每个 key 维护一条按版本递增保存的历史记录，比如用有序数组、时间戳数组加二分查找，或按版本存储 value。PUT 时全局版本号递增，并把新值追加到对应 key 的历史中；查询时若版本号未命中，就返回不晚于该版本的最近一次写入值。