Implement an in-memory key-value store with time-travel (versioned snapshots)

Problem: Implement an in-memory key-value store with time-travel (versioned snapshots) Implement an in-memory key-value store TimeTravelKV that supports writes/deletes, reads at an arbitrary timestamp, and creating/restoring snapshots. You must track state over time so you can answer what value a key had at a given time in the past. Required APIs Design and implement the following interface (typically as a class with methods): put(key: str, value: str, ts: int) -> None Write key=value at timestamp ts. delete(key: str, ts: int) -> None Delete key at timestamp ts. get(key: str, ts: int) -> Optional[str] Return the value of key at time ts (the latest event with time <= ts). Return None if the key does not exist at ts. snapshot(ts: int) -> str Produce a full snapshot of the state at timestamp ts serialized as a string (e.g., JSON). load(snapshot_str: str) -> None Restore state from a snapshot string (you should be able to continue put/delete/get afterwards). Constraints / edge cases Timestamps are integers and may arrive out of order. Multiple writes for the same key at the same timestamp: the last one wins. Be ready to discuss time/space tradeoffs (e.g., per-key sorted history). Scale assumptions Up to about 1e5 operations key/value length up to about 1e3 Example put("a","x", 5) put("a","y", 10) get("a", 7) → "x" delete("a", 12) get("a", 20) → None Provide a runnable implementation plus a few tests. Example Input put a x 5 put a y 10 get a 7 Output x