Medium · System Design

Version control snapshot

Implement VersionControl over a key-value map whose version 0 is empty: set(key, value) creates the next version (the latest map with key set to value), get(key, version) returns (value, true) if key has a value in that version and (0, false) if it does not or the version does not exist, and currentVersion() returns the latest version number.

Examples

Example 1

{
  "ops": [
    {"kind": "set", "key": "a", "value": 1},
    {"kind": "set", "key": "b", "value": 2},
    {"kind": "get", "key": "a", "version": 0},
    {"kind": "get", "key": "b", "version": 1}
  ]
}

Output: [[0, false], [0, false]]

Example 2

{
  "ops": [
    {"kind": "set", "key": "a", "value": 1},
    {"kind": "set", "key": "b", "value": 2},
    {"kind": "set", "key": "a", "value": 9},
    {"kind": "get", "key": "a", "version": 1},
    {"kind": "get", "key": "a", "version": 3},
    {"kind": "get", "key": "b", "version": 1},
    {"kind": "get", "key": "b", "version": 3},
    {"kind": "get", "key": "a", "version": 4},
    {"kind": "currentVersion"}
  ]
}

Output: [[1, true], [9, true], [0, false], [2, true], [0, false], 3]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.