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.

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.

Hints

  1. For each key touched in the current batch, record its old value only the first time that key is edited in the batch.
  2. 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.

Hints

  1. 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.
  2. For later edits to the same key, update only the final value in its compact record.

Loading coding console...