Skip to main content

17. Snapshot Array

mediumAsked at Redis

Implement an array with O(1) set/snap and O(log) snapshot reads; Redis uses it because the data structure mirrors how RDB snapshots cooperate with copy-on-write forks.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement SnapshotArray(length). set(index, val) sets the element. snap() returns the current snap_id and increments. get(index, snap_id) returns the value at that index at that snapshot.

Constraints

  • 1 <= length <= 5 * 10^4
  • 0 <= index < length
  • Up to 5 * 10^4 ops

Examples

Example 1

Input
SnapshotArray(3); set(0,5); snap()=0; set(0,6); get(0,0)=5
Output
[null,null,0,null,5]

Approaches

1. Copy whole array per snap

Push a deep copy of the array into a snapshots array on every snap.

Time
O(length) per snap, O(1) reads
Space
O(length * snaps)
// snap() pushes a structuredClone; get reads from snapshots[snap_id][index].

Tradeoff:

2. Per-index history with binary search

Store per-index list of [snap_id, value]. set appends or updates the current snap entry. get does binary search for the largest snap_id <= target. RDB's copy-on-write fork only diverges on touched pages — same locality idea.

Time
O(1) set, O(log s) get, O(1) snap
Space
O(touched cells)
class SnapshotArray {
  constructor(length) {
    this.snapId = 0;
    this.history = Array.from({ length }, () => [[-1, 0]]);
  }
  set(i, v) {
    const last = this.history[i][this.history[i].length - 1];
    if (last[0] === this.snapId) last[1] = v;
    else this.history[i].push([this.snapId, v]);
  }
  snap() { return this.snapId++; }
  get(i, sid) {
    const arr = this.history[i];
    let lo = 0, hi = arr.length - 1, ans = 0;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid][0] <= sid) { ans = arr[mid][1]; lo = mid + 1; } else hi = mid - 1;
    }
    return ans;
  }
}

Tradeoff:

Redis-specific tips

Redis interviewers reward you for tying snapshot arrays to the RDB fork() + COW semantics; mention how the child only allocates pages for keys that change during BGSAVE.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Snapshot Array and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →