Google·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Google SWE interview with a coding problem centered on a document layer with undo/redo semantics. The problem had a solid follow-up about memory efficiency that I didn't see coming until we were already mid-solution.

Questions Asked (2)

Design a document layer class that stores properties as a string-to-string map and supports beginBatch(), setProperty(), endBatch(), undo(), and redo(). Undo must restore the exact state before the batch, redo must reapply it, and committing a new batch after an undo should clear the redo history.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with two stacks, one for undo and one for redo, and stored a full snapshot of the map at each endBatch() call.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then propose a design that uses a stack of state snapshots or a command pattern to support undo/redo. Explain how batching works by capturing the state before the batch and applying changes atomically, and how redo history is cleared when a new batch is committed after an undo.

Pro tip: Emphasize the trade-offs between memory usage and performance: storing full snapshots is simple but memory-heavy, while storing deltas is efficient but complex. Discuss how you would handle concurrency and atomicity, especially in a distributed system like Google's.

1. Clarify Requirements and Constraints

Ask questions to understand the expected scale, concurrency needs, and whether persistence is required. Confirm that undo/redo should work across batches and that redo history is cleared on new commits.

2. Choose a Core Data Structure

Decide between storing full snapshots of the map or using a command pattern with deltas. Consider using two stacks (undo and redo) to manage history.

3. Design Batch Operations

Implement beginBatch() to start recording changes and capture the current state. endBatch() should commit the batch, push the pre-batch state onto the undo stack, and clear the redo stack.

4. Implement Undo and Redo

undo() should pop from the undo stack, push the current state onto the redo stack, and restore the popped state. redo() should do the reverse.

5. Discuss Trade-offs and Optimizations

Compare snapshot vs. delta approaches in terms of memory and time complexity. Mention potential optimizations like copy-on-write or persistent data structures.

Key Points to Mention

Use of two stacks (undo and redo) to manage history.
Capturing the state before a batch to ensure exact restoration.
Clearing the redo stack when a new batch is committed after an undo.
Trade-offs between full snapshots and delta-based approaches.
Handling concurrency and atomicity, especially in distributed systems.
Time and space complexity of operations (e.g., O(n) for snapshot copy).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Follow-up: make the undo/redo history memory-efficient. If a batch updates the same key multiple times, only record one compact Change entry per key (storing the key, its final value after the batch, its value before the batch, and whether it existed before the batch). How do you build and use this compact structure?

Technical Trade-offsAlgorithms & Data StructuresSystem Design

Author's notes

This is where I kind of scrambled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that you would maintain a per-batch map from key to a compact Change entry, updating it as operations are applied so that only the first 'before' state and the latest 'after' state are kept. Then, when the batch commits, convert this map into a list of Change objects and push it onto the undo stack, while also pushing the inverse onto the redo stack. Emphasize that this reduces memory from O(number of operations) to O(number of distinct keys) and that the same structure can be used for both undo and redo.

Pro tip: Mention that you must capture the 'before' state only on the first modification of a key in the batch, and that you should consider using a persistent or immutable data structure for the history to avoid accidental mutations and to enable efficient snapshots.

1. Define the compact Change structure

Specify that each Change entry stores the key, the value before the batch (or a sentinel if the key didn't exist), the final value after the batch (or a sentinel if deleted), and a boolean indicating prior existence.

2. Build the per-batch map during operations

As each operation in the batch is applied, look up the key in a temporary map. If absent, create a new entry recording the current (pre-operation) value and existence; if present, update only the final value and existence.

3. Finalize and store the batch

When the batch ends, convert the map values into a list of Change objects. Push this list onto the undo stack and push the inverse list (swapping before/after) onto the redo stack.

4. Apply undo/redo using the compact list

To undo, iterate the list and set each key to its 'before' value (or delete if it didn't exist). To redo, set each key to its 'after' value (or delete if it was deleted).

5. Analyze memory and time complexity

Highlight that memory is O(K) where K is the number of distinct keys touched, and time is O(N) for building (N operations) and O(K) for undo/redo, which is optimal for this representation.

Key Points to Mention

Use a hash map (dictionary) keyed by the key to accumulate changes within a batch.
Store sentinel values (e.g., null or a special object) to represent non-existence, and a boolean flag for clarity.
Only the first 'before' state and the last 'after' state per key are needed; intermediate values are discarded.
The same compact structure can be used for both undo and redo by swapping the before/after fields.
Consider thread-safety or concurrency if the data structure is shared, and use immutable entries to prevent accidental modification.
Mention that this approach reduces memory from O(N) to O(K) and is especially beneficial when many operations touch the same key.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.