How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Implement Memory-Efficient Document Undo/Redo

Quick Overview

This question evaluates data structure design and algorithmic reasoning for implementing memory-efficient undo/redo semantics on a key-value document, emphasizing space-efficient per-batch state tracking (storage proportional to distinct keys changed) and correct handling of key creation and deletion.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are implementing a simplified document layer for a design tool. The document is a map from `string key` to `string value`. Implement a data structure that supports these operations: - `apply(key, value)`: immediately update the document so that `document[key] = value`. - `batch()`: close the current batch of changes. All `apply` calls since the previous `batch()` belong to one undoable unit. - `undo()`: revert the most recently closed batch. - `redo()`: reapply the most recently undone batch. Use standard undo/redo semantics: - `apply()` takes effect immediately. - A batch may contain multiple `apply()` calls. - `undo()` reverts the entire last batch at once. - `redo()` reapplies the same batch. - If a new batch is created after an `undo()`, the redo history is cleared. The main requirement is **memory efficiency**. If the same key is updated multiple times within one batch, you should not store every intermediate change. Instead, the memory used by one batch should be proportional to the number of **distinct keys changed in that batch**, not the total number of `apply()` calls. Example: - Initial document: `{ "color": "red" }` - `apply("color", "yellow")` - `apply("color", "pink")` - `batch()` - `undo()` should restore the document to `{ "color": "red" }` - `redo()` should change it back to `{ "color": "pink" }` Also handle keys that did not exist before the batch. If a batch creates a new key, then `undo()` should remove that key entirely. Design the data structures and implement these operations. Discuss the time and space complexity.

Quick Answer: This question evaluates data structure design and algorithmic reasoning for implementing memory-efficient undo/redo semantics on a key-value document, emphasizing space-efficient per-batch state tracking (storage proportional to distinct keys changed) and correct handling of key creation and deletion.

You are implementing a simplified document layer for a design tool (think Figma). The document is a map from `string key` to `string value`. Implement a data structure that supports `apply`, `batch`, `undo`, and `redo`. Operations: - `apply(key, value)`: immediately update the document so that `document[key] = value`. - `batch()`: close the current batch of changes. All `apply` calls since the previous `batch()` form one undoable unit. - `undo()`: revert the entire most recently closed batch at once. - `redo()`: reapply the most recently undone batch. Semantics: - `apply()` takes effect immediately. - A batch may contain multiple `apply()` calls. - If a key is updated several times within one batch, only the **net change** matters: undoing the batch restores the value the key had *before* the batch started. - If a batch creates a brand-new key, undoing the batch removes that key entirely. - Creating a new batch after an `undo()` clears the redo history. - `undo()` with nothing to undo, and `redo()` with nothing to redo, are no-ops. **Memory requirement:** the memory used by one batch must be proportional to the number of **distinct keys changed in that batch**, not the total number of `apply()` calls. The trick is to record, per batch, only the *original* value (and whether the key existed) the first time each key is touched in that batch. Driver contract for this console: implement `solution(operations)`, where `operations` is a list of operations. Each operation is a list: `["apply", key, value]`, `["batch"]`, `["undo"]`, or `["redo"]`. Replay them against your data structure and return the final document as a dictionary (sorted by key). Example: - Initial document is empty. - `apply("color", "yellow")`, `apply("color", "pink")`, `batch()`, then `undo()` -> document is `{}` (the key was newly created, so undo removes it). - A following `redo()` -> `{"color": "pink"}`.

Constraints

Keys and values are non-empty strings.
apply takes effect immediately; multiple applies to the same key in one batch must collapse to a single recorded original value.
undo reverts an entire batch atomically; a batch that created a new key must, on undo, remove that key.
Creating a new batch after an undo clears the redo history.
undo with an empty undo stack and redo with an empty redo stack are no-ops.
Memory per batch must be proportional to the number of distinct keys changed, not the number of apply calls.

Examples

Input: ([['apply', 'color', 'yellow'], ['apply', 'color', 'pink'], ['batch'], ['undo']],)

Expected Output: {}

Explanation: Two applies to 'color' collapse into one batch; the key was newly created, so undo removes it, leaving an empty document.

Input: ([['apply', 'color', 'yellow'], ['apply', 'color', 'pink'], ['batch'], ['undo'], ['redo']],)

Expected Output: {'color': 'pink'}

Explanation: Redo reapplies the net effect of the batch, restoring the final value 'pink' (not the intermediate 'yellow').

Input: ([['apply', 'color', 'yellow']],)

Expected Output: {'color': 'yellow'}

Explanation: apply takes effect immediately even before batch() is called.

Input: ([],)

Expected Output: {}

Explanation: No operations leaves the document empty.

Input: ([['apply', 'a', '1'], ['apply', 'b', '2'], ['batch'], ['apply', 'a', '3'], ['batch'], ['undo']],)

Expected Output: {'a': '1', 'b': '2'}

Explanation: The second batch only changed 'a'; undo reverts 'a' from '3' back to '1', leaving 'b' untouched.

Input: ([['apply', 'a', '1'], ['apply', 'b', '2'], ['batch'], ['apply', 'a', '3'], ['batch'], ['undo'], ['undo']],)

Expected Output: {}

Explanation: Two undos peel off both batches; since both keys were newly created in the first batch, they are removed.

Input: ([['apply', 'x', 'v1'], ['batch'], ['apply', 'x', 'v2'], ['batch'], ['undo'], ['apply', 'x', 'v3'], ['batch'], ['redo']],)

Expected Output: {'x': 'v3'}

Explanation: After undoing the v2 batch, a new committed batch (v3) clears the redo history, so the trailing redo is a no-op.

Input: ([['undo'], ['redo']],)

Expected Output: {}

Explanation: Undo and redo on empty stacks are no-ops.

Input: ([['apply', 'k', 'a'], ['apply', 'k', 'b'], ['apply', 'k', 'c'], ['batch'], ['undo'], ['redo']],)

Expected Output: {'k': 'c'}

Explanation: Three applies to one key within a batch store only the original (none) and net final value 'c'; redo restores 'c'.

Hints

Keep a 'pending' map for the batch currently being built. The first time a key is touched in this batch, store its original value and whether it previously existed; ignore subsequent applies to the same key for memory purposes.
On batch(), push the pending map onto an undo stack and clear it. Pushing a freshly committed batch also clears the redo stack.
On undo(), pop a batch and, for each recorded key, restore its original value (or delete it if it did not exist before). Capture the current values first so redo can reapply them.
Treat undo/redo on empty stacks as no-ops, and remember that a new committed batch after an undo wipes the redo history.

Quick Overview