KV Store with Rollback (Versioned Key-Value Store)

KV Store with Rollback (Versioned Key-Value Store) Design and implement an in-memory key-value store that supports updates and can roll back to a previous checkpoint (version). Supported operations put(key, value): Set key to value. Overwrite if key already exists. get(key): Return the value of key in the current version; return null (or empty) if missing. checkpoint(): Create a new checkpoint (snapshot) and return its version id (an increasing integer). rollback(version): Roll the entire store back to the exact state at the specified checkpoint. Constraints / requirements Version ids returned by checkpoint() may start from 0 or 1, but must be consistent. After rollback, all keys must match exactly what they were at the checkpoint; all changes after that checkpoint must be undone. If rollback(version) is invalid (non-existent/out of range), define a clear behavior (return false/throw/ignore) and implement it. Explain and implement the core data structures behind the APIs. Example test scenarios Expressed as an operation sequence: put(a, 1) v1 = checkpoint() (assume it returns 1) put(a, 2) get(a) => 2 rollback(v1) get(a) => 1 put(b, x) v2 = checkpoint() put(b, y) rollback(v2) get(b) => x Example Input put a 1 checkpoint put a 2 get a rollback 0 get a Output 2 1