## Execute a TTL Key-Value Store with Transactions ### Problem Implement `executeKvCommands(commands) -> outputs` for an in-memory key-value store. Commands are processed in order from logical time `0`. Each command is a homogeneous JSON array of strings whose first element is an uppercase operation name: - `["PUT", key, value]` stores the string `value` under `key` and clears any expiration previously attached to that key. - `["GET", key]` appends the current value to `outputs`, or appends `"NOT FOUND"` if the key does not exist or has expired. - `["DEL", key]` removes the key and any expiration. Deleting a missing key has no effect. - `["SLEEP", t_text]` parses the canonical nonnegative decimal string `t_text` and advances logical time by that amount. It must not scan all keys. - `["EXPIRE", key, ttl_text]` parses the canonical nonnegative decimal string `ttl_text` and replaces the live key's expiration with `current_time + ttl`. Inputs call `EXPIRE` only for a live key. A `ttl_text` of `"0"` expires the key immediately. - `["TTL", key]` appends the remaining lifetime as a base-10 string. It appends `"NONE"` for a live key without an expiration and `"NOT FOUND"` for a missing or expired key. - `["BEGIN"]` starts a transaction. - `["COMMIT"]` keeps all changes made in the active transaction and ends it. - `["ROLLBACK"]` restores every key changed by the active transaction to its state immediately before its first transactional write, then ends the transaction. There is at most one active transaction; inputs never nest `BEGIN`, and `COMMIT` or `ROLLBACK` appears only while a transaction is active. `GET` and `TTL` inside a transaction see earlier writes from that transaction. Values already appended to `outputs` remain there after a rollback. Logical time is global and is not rolled back. A rollback restores both the original value and its original absolute expiration, but that restored key is still absent if the current time has already reached that expiration. ### Function Contract - `commands` is a JSON array of JSON arrays of strings. Every row has exactly the arity shown for its operation. - Keys and values are nonempty JSON strings. - Return one JSON array of strings containing results from `GET` and `TTL` in encounter order. Other commands append no output. - Do not mutate `commands`. The four language signatures use only homogeneous string containers: - Python: `def executeKvCommands(commands: list[list[str]]) -> list[str]` - JavaScript: `function executeKvCommands(commands)` accepts an array of string arrays and returns an array of strings. - Java: `List<String> executeKvCommands(List<List<String>> commands)` - C++: `vector<string> executeKvCommands(const vector<vector<string>>& commands)` ### Constraints - `1 <= commands.length <= 4,000`. - Each key and value contains at most `512` Unicode code points. - Let `B` be the byte length of the entire `commands` array serialized as compact UTF-8 JSON: no whitespace outside strings; quotes, reverse solidus, and control characters use their shortest required JSON escapes; other Unicode is encoded directly as UTF-8; and every bracket, comma, quote, and escape byte is counted. Inputs satisfy `B <= 96,000`. - Every numeric argument is the canonical string `"0"` or matches `[1-9][0-9]*`; signs, whitespace, and leading zeros are not allowed. - Every parsed `t` and `ttl` is at most `9,007,199,254,740,991`. Inputs guarantee that advancing time and computing `current_time + ttl` never exceed this bound. - Every returned remaining lifetime uses the same canonical decimal encoding. - Let `R` be the compact UTF-8 JSON byte length of the returned string array under the same counting rule. Inputs guarantee `R <= 96,000`, including repeated `GET` values and all query sentinels. Thus the fully serialized input plus result is at most `192,000` bytes. - Use absolute expiration times and lazy deletion; `SLEEP` must be `O(1)`. - Hash-map state work is expected `O(1)` per command after accounting for the bytes parsed, hashed, copied, or emitted; end-to-end work must include those string lengths rather than treating them as free. - If a transaction changes `u` distinct keys whose saved pre-transaction states occupy `U` bytes, target `O(u + U)` transaction memory and rollback time. Record a key's pre-transaction state only on its first transactional write. ### Examples ```text commands = [ ["PUT", "a", "one"], ["GET", "a"], ["DEL", "a"], ["GET", "a"] ] outputs = ["one", "NOT FOUND"] ``` ```text commands = [ ["PUT", "a", "one"], ["EXPIRE", "a", "5"], ["TTL", "a"], ["SLEEP", "3"], ["TTL", "a"], ["PUT", "a", "two"], ["TTL", "a"], ["GET", "a"] ] outputs = ["5", "2", "NONE", "two"] ``` ```text commands = [ ["PUT", "a", "old"], ["EXPIRE", "a", "10"], ["BEGIN"], ["PUT", "a", "new"], ["PUT", "b", "temporary"], ["GET", "a"], ["ROLLBACK"], ["GET", "a"], ["GET", "b"], ["TTL", "a"] ] outputs = ["new", "old", "NOT FOUND", "10"] ``` The first `GET` result remains in `outputs` even though the transaction is rolled back. The missing-state sentinel for `b` distinguishes a key that did not exist before the transaction from one whose original value happened to resemble a sentinel string. ```text commands = [ ["PUT", "x", "old"], ["EXPIRE", "x", "4"], ["BEGIN"], ["PUT", "x", "new"], ["SLEEP", "5"], ["ROLLBACK"], ["GET", "x"] ] outputs = ["NOT FOUND"] ``` Rollback restores the original absolute expiration at time `4`; it does not rewind the current time from `5`. ```hint Separate global time from reversible writes Decide which state belongs to an individual key and which state continues to advance outside the transaction. ``` ### Discussion Requirements 1. Explain why decrementing every remaining TTL during `SLEEP` is too expensive. 2. Show why an undo log uses less memory than copying the entire store at `BEGIN`. 3. Explain why the undo state needs a missing-key marker distinct from every valid string value. 4. Describe how lazy expiration interacts with rollback when logical time advances inside a transaction.