Snapshot Array
Medium · Design · Array · Hash Table · Binary Search · Design
Problem
Design an array that can take cheap snapshots of its contents and later read any element as it was at any snapshot.
Implement SnapshotArray:
- SnapshotArray(length) creates an array of length elements, all 0.
- set(index, val) sets the element at index to val.
- snap() takes a snapshot and returns its id: the number of earlier snap calls, so the first id is 0.
- get(index, snap_id) returns the value at index as it was when snapshot snap_id was taken.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ops = ["SnapshotArray","set","snap","set","set","snap","get","get","get"], args = [[3],[1,4],[],[1,8],[2,6],[],[1,0],[1,1],[2,0]] Output: [None, None, 0, None, None, 1, 4, 8, 0]
Index 1 was 4 at snapshot 0 and 8 at snapshot 1; index 2 was still 0 at snapshot 0.
Input: ops = ["SnapshotArray","snap","snap","get"], args = [[1],[],[],[0,1]] Output: [None, 0, 1, 0]
Nothing was ever set, so every read is 0.
Constraints
- 1 <= length <= 5 · 10^4
- 0 <= index < length
- 0 <= val <= 10^9
- 0 <= snap_id < the number of snap() calls so far
- At most 5 · 10^4 calls to set, snap and get in total
Approaches
- Baseline: copy the whole array at every snap — time set O(1), snap O(length), get O(1), space O(length · snaps)
Follow-up
What other questions can snapshots answer cheaply? The total of the array at a snapshot needs only a running total recorded at each snap, and counting how often a slot changed between two snapshots needs a change-only history and two binary searches: see the use cases “Total of the array at a snapshot” and “How often a slot changed between two snapshots”.
Related problems
Start free on Cariara · Coding problems · System design studio
