A fintech platform uses feature flags to safely roll out UI and risk-model changes to millions of daily active users. During an incident, engineers must answer questions like: “What was the flag state at the exact moment snapshot s was taken?”—even after many later updates.
Design a data structure SnapshotArray that behaves like an integer array, but supports immutable snapshots.
Implement the following API:
SnapshotArray(length: int)
length with all values set to 0.set(index: int, val: int) -> None
index to val in the current (not-yet-snapped) version.snap() -> int
snap_id (starting at 0, increasing by 1).get(index: int, snap_id: int) -> int
index as it was when snapshot snap_id was taken.get must return 0 if an index had never been set at or before that snapshot.set calls to the same index before a snap() should be last-write-wins for that snapshot.Example 1
ops = [SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0)]snap() -> 0, get(0,0) -> 50 captured index 0 as 5. The later set(0,6) does not affect reads from snapshot 0.Example 2
ops = [SnapshotArray(2), snap(), get(1,0), set(1,7), snap(), get(1,1), get(1,0)]snap() -> 0, get(1,0) -> 0, snap() -> 1, get(1,1) -> 7, get(1,0) -> 01 is 0 in snapshot 0. After setting it to 7, it becomes visible starting snapshot 1.1 <= length <= 5 * 10^40 <= index < length0 <= val <= 10^90 <= snap_id < number_of_snaps2 * 10^5 total calls across set, snap, and get