Snapshot Array
Asked at Apple, Databricks, Netflix
Problem
Implement a Snapshot Array that supports the following: set(index, val) sets the value at a given index, snap() takes a snapshot and returns the snapshot ID, and get(index, snap_id) returns the value at the given index in the most recent snapshot taken before or at snap_id.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Netflix | Medium | View all Netflix questions → |
How to Think About It
Store history per index: each index has a list of (snap_id, value) pairs. On set(index, val), append (current_snap, val) to that index's history.
On snap(), increment the global snap_id counter. No data is copied, making snap O(1).
On get(index, snap_id), binary search that index's history for the largest snap_id <= the requested snap_id. This finds the most recent value at or before that snapshot.
Visual walkthrough:
snap_id starts at 0.
set(0, 5): history[0] = [(0, 5)]
snap(): snap_id becomes 1.
set(0, 6): history[0] = [(0, 5), (1, 6)]
snap(): snap_id becomes 2.
get(0, 1): binary search history[0] for snap_id <= 1. Found (1, 6). Return 6.
get(0, 0): binary search history[0] for snap_id <= 0. Found (0, 5). Return 5.
Edge cases: get before any set (return 0), multiple sets at same index without snap (each gets same snap_id), get with snap_id = 0 after initial snap.
Optimal Approach
Data structure: array of lists, where each list stores (snap_id, value) pairs.
set(index, val):
Append (current_snap_id, val) to history[index].
snap():
Increment current_snap_id. Return the old value.
get(index, snap_id):
Binary search history[index] for the largest pair with snap_id <= given snap_id.
If found, return its value. Otherwise return 0.
Time: set is O(1). snap is O(1). get is O(log k) where k is the number of sets at that index. Space: O(total_sets).
What Trips People Up in Real Interviews
Copying the entire array on every snap(). This makes snap() O(n) and defeats the purpose. The correct approach is O(1) snap by just incrementing a counter. Each index stores only the changes, not the full array.
Using a single flat list of all snapshots instead of per-index history. A flat list forces O(n) lookup per get() because you must search through every index at each snap. Per-index history limits binary search to only the changes at that index.
Binary searching for exact snap_id match instead of largest snap_id <= target. Values are only recorded when set() is called. Between snaps, the value stays the same. You need the most recent version at or before the requested snap, not an exact match.
Forgetting that multiple set() calls between two snap() calls share the same snap_id. This means history[index] can have consecutive entries with identical snap_id. The binary search must handle this correctly by taking the last entry with snap_id <= target.
Not initializing the result to 0. If no set() has been called at an index before the requested snap, the value is 0 by default. Forgetting this default and returning None or throwing an error fails edge cases.
Solution Code
import bisect
class SnapshotArray:
def __init__(self, length):
self.snap_id = 0
self.history = [[] for _ in range(length)]
def set(self, index, val):
self.history[index].append((self.snap_id, val))
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
history = self.history[index]
lo, hi = 0, len(history) - 1
result = 0
while lo <= hi:
mid = (lo + hi) // 2
if history[mid][0] <= snap_id:
result = history[mid][1]
lo = mid + 1
else:
hi = mid - 1
return resultFrequently Asked Questions
What is the Snapshot Array problem?
Implement a Snapshot Array that supports the following: set(index, val) sets the value at a given index, snap() takes a snapshot and returns the snapshot ID, and get(index, snap_id) returns the value at the given index in the most recent snapshot taken before or at snap_id.
How do you solve Snapshot Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Snapshot Array?
Snapshot Array is asked at Apple, Databricks, Netflix. It is a medium difficulty problem.
What are common mistakes on Snapshot Array?
- Copying the entire array on every `snap()`. This makes `snap()` `O(n)` and defeats the purpose. The correct approach is `O(1)` snap by just incrementing a counter. Each index stores only the changes, not the full array.
- Using a single flat list of all snapshots instead of per-index history. A flat list forces `O(n)` lookup per `get()` because you must search through every index at each snap. Per-index history limits `binary search` to only the changes at that index.
- Binary searching for exact `snap_id` match instead of largest `snap_id <= target`. Values are only recorded when `set()` is called. Between snaps, the value stays the same. You need the most recent version at or before the requested snap, not an exact match.
- Forgetting that multiple `set()` calls between two `snap()` calls share the same `snap_id`. This means `history[index]` can have consecutive entries with identical `snap_id`. The `binary search` must handle this correctly by taking the last entry with `snap_id <= target`.
- Not initializing the result to 0. If no `set()` has been called at an index before the requested snap, the value is 0 by default. Forgetting this default and returning `None` or throwing an error fails edge cases.