FastPrepFastPrep
Problem Brief

KV Store with Rollback

FULLTIMEPHONE SCREEN

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:

  1. String[] operations: the operations to execute in order

Returns

String[]: the output lines produced by the batch.

1Example 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.

2Example 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.

Constraints

Limits and guarantees your solution can rely on.

  • Checkpoint ids are increasing integers.
  • After a rollback, the full store state must match the target checkpoint exactly.
  • Invalid rollback behavior should be handled consistently by the implementation.
public String[] runVersionedKvStore(String[] operations) {
    // write your code here
}
Input

operations

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

Output

["2", "1"]

Sign in to submit your solution.