Feature Flag Snapshot Array Store

Problem

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.

Requirements

Implement the following API:

1. SnapshotArray(length: int)
   • Initializes an array of size length with all values set to 0.
2. set(index: int, val: int) -> None
   • Sets the value at index to val in the current (not-yet-snapped) version.
3. snap() -> int
   • Takes a snapshot of the array and returns the snap_id (starting at 0, increasing by 1).
4. get(index: int, snap_id: int) -> int
   • Returns the value at index as it was when snapshot snap_id was taken.

Notes / Clarifications

• get must return 0 if an index had never been set at or before that snapshot.
• Multiple set calls to the same index before a snap() should be last-write-wins for that snapshot.
• Your solution must be memory-efficient: avoid copying the entire array on each snapshot.

Constraints

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < number_of_snaps
• At most 2 * 10^5 total calls across set, snap, and get