Memento pattern in LLD - System Design Exercise

Design: Memento Pattern Implementation

Design the core components of the Memento pattern including Originator, Memento, and Caretaker. Out of scope are UI undo/redo integration and persistence of states beyond runtime.

Functional Requirements

FR1: Allow an object to save its state at a point in time.

FR2: Enable restoring the object to a previous saved state.

FR3: Keep the saved state separate from the object's main logic.

FR4: Support multiple saved states for undo functionality.

FR5: Ensure the saved states are immutable once created.

Non-Functional Requirements

NFR1: The system should handle up to 1000 saved states per object.

NFR2: Restoring a state should happen within 10 milliseconds.

NFR3: Memory usage should be optimized to avoid storing full copies if possible.

NFR4: The design should keep the originator's internal state encapsulated.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Originator: the object whose state is saved and restored

Memento: the object that stores the saved state

Caretaker: manages saved states and controls undo/redo

State storage mechanism: in-memory list or stack

Design Patterns

Command pattern for undo/redo operations

Prototype pattern for cloning state

Flyweight pattern to optimize memory for repeated state parts

Reference Architecture

Originator <--> Memento
Caretaker manages Memento stack

+------------+       +------------+       +------------+
| Originator |<----->|  Memento   |<----->| Caretaker  |
+------------+       +------------+       +------------+

Components

Originator

Any OO language

Creates a memento containing a snapshot of its current internal state and uses mementos to restore its state.

Memento

Immutable object

Stores the internal state of the Originator. It is immutable and only accessible by the Originator.

Caretaker

In-memory stack or list

Keeps track of saved mementos and provides undo/redo functionality by restoring states.

Request Flow

1. 1. Originator creates a Memento capturing its current state.

2. 2. Caretaker receives and stores the Memento in a stack.

3. 3. When undo is requested, Caretaker retrieves the last Memento.

4. 4. Originator restores its state from the retrieved Memento.

5. 5. Repeat for multiple undo steps as needed.

Database Schema

Not applicable as this pattern typically uses in-memory objects. Key entities: Originator (has state), Memento (stores snapshot), Caretaker (manages Memento collection).

Scaling Discussion

Bottlenecks

Memory usage grows linearly with number of saved states.

Restoring large complex states may cause latency spikes.

Managing many saved states can slow down undo/redo operations.

Solutions

Use incremental or differential snapshots to save only changes between states.

Limit the number of saved states with a fixed-size stack or pruning strategy.

Compress or serialize states efficiently to reduce memory footprint.

Use lazy restoration or background processing for heavy state restores.

Interview Tips

Time: Spend 10 minutes explaining the pattern and components, 15 minutes designing the interaction and data flow, 5 minutes discussing scaling and optimizations, and 5 minutes for questions.

Explain separation of concerns: Originator vs Memento vs Caretaker.

Highlight immutability of Memento to protect state integrity.

Discuss how this pattern supports undo functionality.

Mention memory and performance considerations.

Show understanding of when and why to use this pattern.

Practice

1. What is the main purpose of the Memento pattern in system design?

easy

A. To create multiple instances of an object efficiently

B. To convert one interface to another compatible interface

C. To manage concurrent access to shared resources

D. To save and restore an object's state without exposing its internal details

Solution

1. Step 1: Understand the role of Memento pattern

   The Memento pattern is designed to capture and externalize an object's internal state so that it can be restored later without exposing the object's implementation details.

2. Step 2: Compare with other design patterns

   Other options describe different patterns: A is about object creation (Factory), C is about synchronization (Mutex), D is about interface compatibility (Adapter).

3. Final Answer:

   To save and restore an object's state without exposing its internal details -> Option D

4. Quick Check:

   Memento = Save & Restore State [OK]

Hint: Memento = save state secretly, no details shown [OK]

Common Mistakes:

• Confusing Memento with Factory or Adapter patterns
• Thinking it manages concurrency
• Assuming it changes object interfaces

2. Which of the following correctly represents the key components of the Memento pattern?

easy

A. Subject, Observer, ConcreteObserver

B. Originator, Memento, Caretaker

C. Client, Proxy, RealSubject

D. Component, Decorator, ConcreteComponent

Solution

1. Step 1: Identify components of Memento pattern

   The Memento pattern consists of three main parts: Originator (the object whose state is saved), Memento (the object storing the state), and Caretaker (manages mementos).

2. Step 2: Eliminate other patterns

   Options B, C, and D correspond to Observer, Proxy, and Decorator patterns respectively, which are unrelated to Memento.

3. Final Answer:

   Originator, Memento, Caretaker -> Option B

4. Quick Check:

   Components = Originator + Memento + Caretaker [OK]

Hint: Remember 3 parts: Originator, Memento, Caretaker [OK]

Common Mistakes:

• Mixing Memento components with Observer or Proxy
• Forgetting the Caretaker role
• Confusing Memento with Decorator pattern

3. Consider this simplified Python code using the Memento pattern:

class Memento:
    def __init__(self, state):
        self._state = state

class Originator:
    def __init__(self):
        self._state = ""
    def set_state(self, state):
        self._state = state
    def save(self):
        return Memento(self._state)
    def restore(self, memento):
        self._state = memento._state

originator = Originator()
originator.set_state("State1")
memento = originator.save()
originator.set_state("State2")
originator.restore(memento)
print(originator._state)

What will be printed?

medium

A. None

B. State2

C. State1

D. Error

Solution

1. Step 1: Trace state changes in Originator

   Initially, Originator's state is set to "State1". Then a Memento is saved capturing "State1". Next, state changes to "State2".

2. Step 2: Restore state from Memento

   Calling restore with the saved Memento sets the state back to "State1". The print statement outputs the restored state.

3. Final Answer:

   State1 -> Option C

4. Quick Check:

   Restore resets state to saved value [OK]

Hint: Restore sets state back to saved snapshot [OK]

Common Mistakes:

• Assuming print shows latest state before restore
• Confusing save and restore methods
• Expecting error due to private variable access

4. In the following code snippet, what is the main issue that breaks the Memento pattern?

class Originator:
    def __init__(self):
        self._state = ""
    def set_state(self, state):
        self._state = state
    def save(self):
        return self._state  # returns state directly
    def restore(self, memento):
        self._state = memento

originator = Originator()
originator.set_state("State1")
memento = originator.save()
originator.set_state("State2")
originator.restore(memento)
print(originator._state)

medium

A. The save method returns state directly, exposing internal details

B. The restore method does not update the state

C. The Originator class lacks a Memento class

D. The set_state method is missing

Solution

1. Step 1: Analyze the save method

   The save method returns the internal state directly instead of encapsulating it in a Memento object, exposing internal details.

2. Step 2: Understand Memento pattern principle

   The pattern requires hiding the internal state inside a Memento object to prevent external access. Returning raw state breaks encapsulation.

3. Final Answer:

   The save method returns state directly, exposing internal details -> Option A

4. Quick Check:

   Save must hide state in Memento [OK]

Hint: Save must return Memento, not raw state [OK]

Common Mistakes:

• Thinking restore method is faulty
• Believing Memento class is mandatory in code
• Ignoring encapsulation principle

5. You are designing a text editor with undo functionality using the Memento pattern. Which approach best balances memory usage and undo capability?

hard

A. Store a Memento only after significant changes or at checkpoints

B. Store a Memento after every single character change

C. Store all changes as raw text snapshots without Memento objects

D. Do not store any state; rely on user to retype

Solution

1. Step 1: Consider memory and undo tradeoff

   Storing a Memento after every character change (Store a Memento after every single character change) uses excessive memory and is inefficient.

2. Step 2: Evaluate checkpoint strategy

   Storing Mementos after significant changes or checkpoints (Store a Memento only after significant changes or at checkpoints) reduces memory use while allowing meaningful undo steps.

3. Step 3: Assess other options

   Store all changes as raw text snapshots without Memento objects wastes memory by storing raw snapshots without encapsulation; Do not store any state; rely on user to retype removes undo capability.

4. Final Answer:

   Store a Memento only after significant changes or at checkpoints -> Option A

5. Quick Check:

   Checkpoint Mementos balance memory and undo [OK]

Hint: Save states at checkpoints, not every keystroke [OK]

Common Mistakes:

• Saving state too frequently causing memory bloat
• Ignoring encapsulation by storing raw snapshots
• Not implementing undo at all