Implement a set that supports `add(value)`, `remove(value)`, `contains(value)`, `snapshot()`, and `containsAt(snapshot_id, value)`. Creating a snapshot returns a monotonically increasing ID representing the exact set state at that moment. Later mutations must not change old snapshot results. Discuss at least two storage strategies and select one for a workload with many mutations but relatively few snapshot reads. ### Constraints & Assumptions - Adding an existing value and removing an absent value are no-ops. - Snapshot IDs remain valid for the lifetime of the structure unless an explicit retention policy is added. - Values are hashable and equality is stable. ### Clarifying Questions to Ask - Must snapshots be iterable, or is point lookup enough? - How many snapshots and unique values are expected? - Is the structure single-threaded? ```hint Preserve old answers economically A later add or remove must not change any existing snapshot result, while snapshot creation should avoid copying the entire current set. ``` ### What a Strong Answer Covers - Snapshot semantics, idempotent mutations, version assignment, and old-version lookup. - Full-copy, copy-on-write, or per-key history trade-offs. - Complexity, memory growth, garbage collection, and concurrency boundaries. ### Follow-up Questions - How would you iterate all values in a snapshot? - How would deleting old snapshots reclaim history safely? - How would lock-free readers affect the design?