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 Batched Undo/Redo Layer | Google Coding Question

Implement Batched Undo/Redo Layer

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 layer stores properties as a `map<string, string>`. Implement a class that supports the following operations: - `beginBatch()`: start a batch of edits. - `setProperty(key, value)`: set or overwrite a property inside the current batch. - `endBatch()`: commit the batch as one undoable action. - `undo()`: revert the most recently committed batch. - `redo()`: reapply the most recently undone batch. Requirements: 1. A batch may update the same key multiple times. 2. `undo()` must restore the exact document state from before that batch. 3. `redo()` must restore the exact document state after that batch. 4. If a property did not exist before the batch, then `undo()` should remove that property. 5. If `undo()` has been called and then a new batch is committed, the redo history must be cleared. 6. Follow-up: make the history memory-efficient. Instead of storing every intermediate edit in a batch, compact the batch so that each key appears at most once in history while still preserving enough information for correct `undo()` and `redo()`. A useful compact record for one key is: ```text Change { string key; string value; // final value after the batch string old_value; // value before the batch bool has_old_value; // whether the key existed before the batch } ``` Explain how you would build and use such a compact history so that repeated updates to the same key inside one batch do not waste memory.

Quick Answer: This question evaluates understanding of state management, undo/redo semantics, batched transactional edits, and memory-efficient change history representation for map-based document layers.

Part 1: Implement Batched Undo/Redo for Document Properties

You are given a sequence of operations for an initially empty document represented as a map<string, string>. A batch starts with ('begin',), contains zero or more ('set', key, value) operations, and ends with ('end',). Each committed batch must be undoable and redoable as one unit. Operation ('snapshot',) asks you to append the current document to the answer; snapshots may appear while a batch is open and should reflect the live document state. If a key is set multiple times in one batch, undo must restore the value from before the batch began. If a key did not exist before the batch, undo must remove it. If a new non-empty batch is committed after an undo, the redo history is cleared. If undo or redo is impossible, do nothing. If end closes an empty batch, treat it as a no-op.

Constraints

0 <= len(operations) <= 200000
The total number of ('set', key, value) operations is at most 200000
Keys and values are strings of length 1 to 50
Batches are not nested
If a batch contains no set operations, committing it does not create history

Examples

Input: [('begin',), ('set', 'color', 'red'), ('end',), ('snapshot',), ('undo',), ('snapshot',), ('redo',), ('snapshot',)]

Expected Output: [{'color': 'red'}, {}, {'color': 'red'}]

Explanation: A single batch is committed, undone, and redone.

Input: [('begin',), ('set', 'a', '1'), ('end',), ('begin',), ('set', 'a', '2'), ('set', 'a', '3'), ('set', 'b', '9'), ('end',), ('snapshot',), ('undo',), ('snapshot',), ('redo',), ('snapshot',)]

Expected Output: [{'a': '3', 'b': '9'}, {'a': '1'}, {'a': '3', 'b': '9'}]

Explanation: The second batch updates 'a' twice and adds 'b'. Undo must restore the exact pre-batch state.

Input: [('begin',), ('set', 'x', '1'), ('end',), ('begin',), ('set', 'y', '2'), ('end',), ('undo',), ('begin',), ('set', 'z', '3'), ('end',), ('redo',), ('snapshot',)]

Expected Output: [{'x': '1', 'z': '3'}]

Explanation: After undoing the batch that added 'y', committing a new batch clears redo history, so redo does nothing.

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

Expected Output: [{}]

Explanation: Edge case: undo and redo on empty history are no-ops.

Input: [('begin',), ('set', 'a', '1'), ('snapshot',), ('set', 'a', '2'), ('snapshot',), ('end',), ('undo',), ('snapshot',)]

Expected Output: [{'a': '1'}, {'a': '2'}, {}]

Explanation: Snapshots inside an open batch should reflect live edits, but undo still reverts the whole committed batch.

Hints

For each key touched in the current batch, record its old value only the first time that key is edited in the batch.
Use two stacks: one for committed batches that can be undone, and one for undone batches that can be redone. Clear the redo stack when a new non-empty batch is committed.

Part 2: Compact a Batch into Memory-Efficient Change Records

You are given the document state before a batch and the raw setProperty edits that happened inside that batch. Multiple edits may target the same key. Build a compact history so that each key appears at most once, while still storing enough information for correct undo and redo. For each touched key, store a record (key, final_value, old_value_or_None, had_old_value). The records must be returned in the order each key first appears in the batch. Then use only these compact records to compute the document after applying the batch, after undoing the batch, and after redoing the batch. There is no delete operation in this problem.

Constraints

0 <= len(initial_document) <= 200000
0 <= len(edits) <= 200000
Keys and values are strings of length 1 to 50
Each edit is a set operation only
The output order of 'changes' must follow the first time each key appears in edits

Examples

Input: ({'a': '1', 'b': '2'}, [('a', '3'), ('a', '4'), ('c', '5')])

Expected Output: {'changes': [('a', '4', '1', True), ('c', '5', None, False)], 'after_apply': {'a': '4', 'b': '2', 'c': '5'}, 'after_undo': {'a': '1', 'b': '2'}, 'after_redo': {'a': '4', 'b': '2', 'c': '5'}}

Explanation: Repeated edits to 'a' collapse into one record that keeps the original old value and the final new value.

Input: ({}, [('x', '1'), ('x', '2'), ('x', '3')])

Expected Output: {'changes': [('x', '3', None, False)], 'after_apply': {'x': '3'}, 'after_undo': {}, 'after_redo': {'x': '3'}}

Explanation: Edge case: a new key is written multiple times in an otherwise empty document.

Input: ({'k': 'v'}, [])

Expected Output: {'changes': [], 'after_apply': {'k': 'v'}, 'after_undo': {'k': 'v'}, 'after_redo': {'k': 'v'}}

Explanation: Edge case: an empty batch produces no compact records and changes nothing.

Input: ({'p': '7', 'q': '8'}, [('r', '1'), ('p', '9'), ('r', '2'), ('q', '0'), ('p', '10')])

Expected Output: {'changes': [('r', '2', None, False), ('p', '10', '7', True), ('q', '0', '8', True)], 'after_apply': {'p': '10', 'q': '0', 'r': '2'}, 'after_undo': {'p': '7', 'q': '8'}, 'after_redo': {'p': '10', 'q': '0', 'r': '2'}}

Explanation: The compact record list follows first appearance order: r, p, q.

Hints

When a key appears for the first time in the batch, capture its old value from the pre-batch document, not from any earlier edit in the same batch.
For later edits to the same key, update only the final value in its compact record.

Quick Overview

This question evaluates understanding of state management, undo/redo semantics, batched transactional edits, and memory-efficient change history representation for map-based document layers.