KV Store with Rollback

Design and implement an in-memory key-value store that supports version checkpoints and rollback. Supported operations are:

• PUT <key> <value>
• GET <key>
• CHECKPOINT
• ROLLBACK <version> CHECKPOINT creates a new snapshot version. ROLLBACK version restores the store to the exact state at that checkpoint. Return the lines printed by the command sequence. Only GET outputs are required in the examples below. Function Description Complete the function runVersionedKvStore in the editor below. runVersionedKvStore has the following parameter:
• String[] operations: the operations to execute in order Returns String[]: the output lines produced by the batch.

Constraints

• Checkpoint ids are increasing integers.
• After a rollback,

Example 1

Input:

operations = ["PUT a 1", "CHECKPOINT", "PUT a 2", "GET a", "ROLLBACK 0", "GET a"]

Output:

["2", "1"]

Explanation: The first GET sees the updated value 2. After rolling back to the first checkpoint, a returns to 1.

Example 2

Input:

operations = ["PUT x 5", "CHECKPOINT", "PUT y 9", "CHECKPOINT", "PUT x 7", "ROLLBACK 1", "GET x", "GET y"]

Output:

["5", "9"]

Explanation: Rolling back to version 1 restores the snapshot created after y was added but before x was changed to 7.