Snapshot Array

Medium · Binary Search · about 25 minutes

Asked at Google, Amazon, Apple, MongoDB, Uber.

Implement an array that supports snapshots.

  • SnapshotArray(length) creates an array of length zeros.
  • set(index, val) sets the element at index.
  • snap() takes a snapshot and returns its id: the first snapshot is 0, the next 1, and so on.
  • get(index, snap_id) returns the value at index when snapshot snap_id was taken.

Related guides