Medium · System Design

Snapshot Array

Implement SnapshotArray(length), an array of length zeros with set(index, val), snap() — which takes a snapshot and returns its id (the number of earlier snap calls) — and get(index, snapId), which returns the value index held when snapshot snapId was taken.

Examples

Example 1

{
  "length": 3,
  "ops": [
    {"kind": "set", "index": 0, "val": 5},
    {"kind": "snap"},
    {"kind": "set", "index": 0, "val": 6},
    {"kind": "get", "index": 0, "snapId": 0}
  ]
}

Output: [0, 5]

Example 2

{
  "length": 2,
  "ops": [
    {"kind": "set", "index": 0, "val": 4},
    {"kind": "set", "index": 0, "val": 7},
    {"kind": "snap"},
    {"kind": "snap"},
    {"kind": "set", "index": 0, "val": 9},
    {"kind": "snap"},
    {"kind": "get", "index": 0, "snapId": 1},
    {"kind": "get", "index": 0, "snapId": 2},
    {"kind": "get", "index": 1, "snapId": 2},
    {"kind": "get", "index": 0, "snapId": 0}
  ]
}

Output: [0, 1, 2, 7, 9, 0, 7]

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.