Problem 73 · Object & System Design

Snapshot Array

MediumClassic DSA & systems

01Problem

Implement SnapshotArray(length) with set(index, val), snap() returning a snapshot id, and get(index, snap_id) returning the value at that index when that snapshot was taken.

02Key insight

Don't copy the array per snapshot. Store per-index a list of (snap_id, value) changes; snap just increments a counter, and get binary-searches the last change at or before snap_id.

03Solution

solution.pypython23 lines

import bisect


class SnapshotArray:
    def __init__(self, length: int) -> None:
        self.snap_id = 0
        self.history: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        h = self.history[index]
        if h[-1][0] == self.snap_id:
            h[-1] = (self.snap_id, val)  # overwrite within the same snap epoch
        else:
            h.append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        h = self.history[index]
        i = bisect.bisect_right(h, (snap_id, float("inf"))) - 1
        return h[i][1]

Try it first.

TimeO(1) set/snap; O(log S) get

SpaceO(length + sets)

tests.py · 5 passing

tests.pypython8 lines

sa = SnapshotArray(3)
sa.set(0, 5)
assert sa.snap() == 0
sa.set(0, 6); sa.set(0, 7)
assert sa.get(0, 0) == 5 and sa.get(1, 0) == 0
assert sa.snap() == 1
assert sa.get(0, 1) == 7 and sa.get(0, 0) == 5
assert len(sa.history[0]) == 3

04Staff-level follow-up

This is the core of MVCC/time-travel tables (Snowflake Time Travel, Delta Lake versions): copy-on-write per changed unit, plus a retention window to garbage-collect versions no reader can see.