Prototype Pattern - Deep Copy vs Shallow Copy

🎯

Prototype Pattern - Deep Copy vs Shallow Copy

mediumOOPAmazonGoogleFlipkart

Imagine you have a complex object representing a user profile with nested preferences and settings. You want to create a copy of this profile to experiment with changes without affecting the original. How do you ensure the copy is independent?

💡 This problem deals with how to create copies of objects in object-oriented programming. Beginners often confuse shallow and deep copies, leading to bugs where changes to one object unexpectedly affect another. Understanding the difference is crucial for safe object cloning.

📋

Problem Statement

Given an object with nested objects or references, implement cloning functionality that supports both shallow copy and deep copy. The shallow copy duplicates the top-level object but shares references to nested objects, while the deep copy duplicates the entire object graph, creating independent nested objects. Implement and demonstrate both approaches.

Objects may contain nested objects or collectionsNested objects can be arbitrarily deepAvoid infinite loops in case of cyclic references (optional advanced)Focus on correctness over performance for deep copy

💡

Example

Input"Original object with nested list: obj = {name: 'A', scores: [10, 20]}"

OutputShallow copy: copy.scores is same reference as obj.scores; Deep copy: copy.scores is a new list with same values

In shallow copy, modifying copy.scores affects obj.scores; in deep copy, they are independent.

• Object with no nested references → shallow and deep copy behave similarly
• Object with nested mutable objects → shallow copy shares references, deep copy duplicates
• Empty object or null references → copying should handle gracefully
• Object with cyclic references (advanced) → deep copy must avoid infinite recursion

⚠️

Common Mistakes

Using shallow copy when deep copy is needed

Modifying nested objects in copy affects original, causing bugs

✅ Implement deep copy to duplicate nested objects

Modifying original after copying without realizing shared references

Unexpected side effects in copied object

✅ Use deep copy or avoid modifying shared nested objects

Not overriding clone or copy methods properly

Default shallow copy used, causing subtle bugs

✅ Override clone/copy methods to implement deep copy logic

Using JSON serialization for deep copy with functions or special objects

Loss of methods or incorrect copying

✅ Use custom clone methods or libraries that handle complex types

Ignoring cyclic references in deep copy

Infinite recursion or stack overflow

✅ Implement memoization to track visited objects during deep copy

🧠

Brute Force: Manual Shallow Copy Implementation

💡 Starting with a manual shallow copy helps understand what copying means at the object level and why it can be insufficient when nested objects are involved.

Intuition

Copy the top-level object fields directly, but nested objects remain shared references. This is simple but can cause side effects if nested objects are modified.

Algorithm

1. Create a new object instance of the same class.
2. Copy primitive fields and references of nested objects directly.
3. Return the new object as the shallow copy.

💡 This approach is straightforward but does not handle nested objects properly, which is a common pitfall.

</>

Code

class Profile:
    def __init__(self, name, scores):
        self.name = name
        self.scores = scores  # list

    def shallow_copy(self):
        # Create a new Profile with same name and same scores reference
        return Profile(self.name, self.scores)

# Driver code
if __name__ == '__main__':
    original = Profile('Alice', [10, 20])
    copy = original.shallow_copy()
    print('Original scores:', original.scores)
    print('Copy scores:', copy.scores)
    copy.scores.append(30)
    print('After modifying copy scores:')
    print('Original scores:', original.scores)
    print('Copy scores:', copy.scores)

Line Notes

def shallow_copy(self):Defines the method to create a shallow copy of the object

return Profile(self.name, self.scores)Copies primitive and references directly, no new nested objects created

copy.scores.append(30)Modifies the nested list in the copy to show shared reference effect

print('Original scores:', original.scores)Shows that original object's nested list is affected by copy's modification

import java.util.*;
class Profile {
    String name;
    List<Integer> scores;

    Profile(String name, List<Integer> scores) {
        this.name = name;
        this.scores = scores;
    }

    Profile shallowCopy() {
        // Shallow copy: new Profile with same scores reference
        return new Profile(this.name, this.scores);
    }

    public static void main(String[] args) {
        List<Integer> scores = new ArrayList<>(Arrays.asList(10, 20));
        Profile original = new Profile("Alice", scores);
        Profile copy = original.shallowCopy();
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
        copy.scores.add(30);
        System.out.println("After modifying copy scores:");
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
    }
}

Line Notes

Profile shallowCopy() {Method to create a shallow copy of the Profile object

return new Profile(this.name, this.scores);Copies references directly, nested list is shared

copy.scores.add(30);Modifies the nested list in the copy to demonstrate shared reference

System.out.println("Original scores: " + original.scores);Shows original object's nested list is affected

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Profile {
public:
    string name;
    vector<int> scores;

    Profile(string n, vector<int> s) : name(n), scores(s) {}

    Profile shallowCopy() {
        // Note: In C++, vector copy is deep by default.
        // This means this method actually performs a deep copy of scores.
        // True shallow copy would require sharing pointer/reference, which is unsafe here.
        return Profile(name, scores); // Copies vector deeply in C++
    }
};

int main() {
    vector<int> scores = {10, 20};
    Profile original("Alice", scores);
    Profile copy = original.shallowCopy();
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy.scores) cout << x << " ";
    cout << endl;
    copy.scores.push_back(30);
    cout << "After modifying copy scores:" << endl;
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy.scores) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

Profile shallowCopy() {Defines shallow copy method; vector copy is deep by default in C++

return Profile(name, scores);Returns new object with copied vector (actually deep copy in C++)

copy.scores.push_back(30);Modifies copy's scores vector to test independence

for (int x : original.scores)Prints original scores to check if affected by copy's modification

class Profile {
    constructor(name, scores) {
        this.name = name;
        this.scores = scores; // array reference
    }

    shallowCopy() {
        // Shallow copy: new object with same array reference
        return new Profile(this.name, this.scores);
    }
}

// Driver code
const original = new Profile('Alice', [10, 20]);
const copy = original.shallowCopy();
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);
copy.scores.push(30);
console.log('After modifying copy scores:');
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);

Line Notes

shallowCopy() {Defines shallow copy method returning new object with shared nested array

return new Profile(this.name, this.scores);Copies primitive and references directly, no new nested array

copy.scores.push(30);Modifies nested array in copy to show shared reference effect

console.log('Original scores:', original.scores);Shows original object's nested array is affected

⏱

Complexity

TimeO(1) since only references are copied, no nested objects duplicated

SpaceO(1) additional space as no new nested objects created

Shallow copy duplicates only top-level object; nested references remain shared, so copying is fast but risky. Note: In C++, vector copy is deep by default, so this approach behaves differently.

💡 For a nested list of size 1000, shallow copy just copies the reference instantly, so it's very fast but can cause bugs if nested objects are modified.

Interview Verdict: Accepted for shallow copy demonstration; insufficient for independent nested objects. Note: C++ vector copy is deep, so true shallow copy is not demonstrated here.

This approach is useful to introduce the concept but not safe for nested mutable objects. C++ behavior differs due to vector semantics.

🧠

Better: Deep Copy Using Recursion

💡 This approach introduces recursion to create independent copies of nested objects, solving the shared reference problem of shallow copy.

Intuition

Recursively copy each nested object or collection to create a fully independent clone of the entire object graph.

Algorithm

1. Check if the field is a primitive or immutable; if yes, copy directly.
2. If the field is a list or collection, create a new list and recursively deep copy each element.
3. If the field is an object, recursively call deep copy on it.
4. Return the new object with all fields deeply copied.

💡 Recursion can be tricky to implement correctly, especially handling different data types and avoiding infinite loops.

</>

Code

import copy

class Profile:
    def __init__(self, name, scores):
        self.name = name
        self.scores = scores

    def deep_copy(self):
        # Use recursion or copy.deepcopy
        new_scores = [score for score in self.scores]  # copy list elements
        return Profile(self.name, new_scores)

# Driver code
if __name__ == '__main__':
    original = Profile('Alice', [10, 20])
    copy = original.deep_copy()
    print('Original scores:', original.scores)
    print('Copy scores:', copy.scores)
    copy.scores.append(30)
    print('After modifying copy scores:')
    print('Original scores:', original.scores)
    print('Copy scores:', copy.scores)

Line Notes

def deep_copy(self):Defines method to create a deep copy of the object

new_scores = [score for score in self.scores]Creates a new list copying each element to avoid shared reference

return Profile(self.name, new_scores)Returns new Profile with independent nested list

copy.scores.append(30)Modifies copy's nested list to verify original is unaffected

import java.util.*;
class Profile {
    String name;
    List<Integer> scores;

    Profile(String name, List<Integer> scores) {
        this.name = name;
        this.scores = scores;
    }

    Profile deepCopy() {
        // Deep copy: create new list and copy elements
        List<Integer> newScores = new ArrayList<>();
        for (Integer score : this.scores) {
            newScores.add(score);
        }
        return new Profile(this.name, newScores);
    }

    public static void main(String[] args) {
        List<Integer> scores = new ArrayList<>(Arrays.asList(10, 20));
        Profile original = new Profile("Alice", scores);
        Profile copy = original.deepCopy();
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
        copy.scores.add(30);
        System.out.println("After modifying copy scores:");
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
    }
}

Line Notes

Profile deepCopy() {Defines method to create a deep copy of the Profile object

List<Integer> newScores = new ArrayList<>();Creates new list to hold copied elements

newScores.add(score);Copies each element individually to avoid shared references

copy.scores.add(30);Modifies copy's list to verify original is unaffected

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Profile {
public:
    string name;
    vector<int> scores;

    Profile(string n, vector<int> s) : name(n), scores(s) {}

    Profile deepCopy() {
        // Deep copy: vector copy is deep by default
        vector<int> newScores = scores; // copies vector elements
        return Profile(name, newScores);
    }
};

int main() {
    vector<int> scores = {10, 20};
    Profile original("Alice", scores);
    Profile copy = original.deepCopy();
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy.scores) cout << x << " ";
    cout << endl;
    copy.scores.push_back(30);
    cout << "After modifying copy scores:" << endl;
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy.scores) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

Profile deepCopy() {Defines deep copy method; vector copy is deep by default in C++

vector<int> newScores = scores;Copies vector elements to new vector for independence

copy.scores.push_back(30);Modifies copy's vector to verify original is unaffected

for (int x : original.scores)Prints original scores to confirm no change

class Profile {
    constructor(name, scores) {
        this.name = name;
        this.scores = scores;
    }

    deepCopy() {
        // Deep copy: create new array copying each element
        const newScores = this.scores.slice();
        return new Profile(this.name, newScores);
    }
}

// Driver code
const original = new Profile('Alice', [10, 20]);
const copy = original.deepCopy();
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);
copy.scores.push(30);
console.log('After modifying copy scores:');
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);

Line Notes

deepCopy() {Defines deep copy method creating independent nested array

const newScores = this.scores.slice();Copies array elements to new array to avoid shared reference

return new Profile(this.name, newScores);Returns new Profile with independent nested array

copy.scores.push(30);Modifies copy's array to verify original is unaffected

⏱

Complexity

TimeO(n) where n is size of nested collections

SpaceO(n) additional space for new nested objects

Deep copy duplicates nested objects, so time and space scale with nested data size.

💡 For a nested list of size 1000, deep copy creates a new list of 1000 elements, which takes more time and memory.

Interview Verdict: Accepted and recommended for safe cloning of nested objects

This approach is the standard way to avoid bugs from shared references in nested objects.

🧠

Optimal: Using Built-in or Language-Specific Clone/Copy Utilities

💡 Many languages provide built-in utilities or interfaces to perform cloning efficiently and correctly, reducing manual errors and boilerplate.

Intuition

Leverage language features like copy constructors, clone interfaces, or serialization to implement deep copy cleanly and reliably.

Algorithm

1. Implement or use the language's clone or copy interface.
2. For deep copy, override clone method to recursively clone nested objects.
3. Use serialization/deserialization if supported to clone entire object graph.
4. Return the cloned object.

💡 This approach abstracts away manual copying details and reduces bugs, but requires understanding language-specific features.

</>

Code

import copy

class Profile:
    def __init__(self, name, scores):
        self.name = name
        self.scores = scores

    def __deepcopy__(self, memo):
        # Use copy.deepcopy for nested objects
        new_name = copy.deepcopy(self.name, memo)
        new_scores = copy.deepcopy(self.scores, memo)
        return Profile(new_name, new_scores)

# Driver code
if __name__ == '__main__':
    original = Profile('Alice', [10, 20])
    copy_obj = copy.deepcopy(original)
    print('Original scores:', original.scores)
    print('Copy scores:', copy_obj.scores)
    copy_obj.scores.append(30)
    print('After modifying copy scores:')
    print('Original scores:', original.scores)
    print('Copy scores:', copy_obj.scores)

Line Notes

def __deepcopy__(self, memo):Overrides deepcopy protocol to customize deep copy behavior

new_name = copy.deepcopy(self.name, memo)Deep copies primitive or nested fields safely

new_scores = copy.deepcopy(self.scores, memo)Deep copies nested list to avoid shared references

copy_obj.scores.append(30)Modifies copy's nested list to verify original is unaffected

import java.util.*;
class Profile implements Cloneable {
    String name;
    List<Integer> scores;

    Profile(String name, List<Integer> scores) {
        this.name = name;
        this.scores = scores;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        // Deep clone: clone nested list
        List<Integer> newScores = new ArrayList<>(this.scores);
        return new Profile(this.name, newScores);
    }

    public static void main(String[] args) throws CloneNotSupportedException {
        List<Integer> scores = new ArrayList<>(Arrays.asList(10, 20));
        Profile original = new Profile("Alice", scores);
        Profile copy = (Profile) original.clone();
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
        copy.scores.add(30);
        System.out.println("After modifying copy scores:");
        System.out.println("Original scores: " + original.scores);
        System.out.println("Copy scores: " + copy.scores);
    }
}

Line Notes

class Profile implements Cloneable {Implements Cloneable interface to enable cloning

protected Object clone() throws CloneNotSupportedException {Overrides clone method to customize cloning

List<Integer> newScores = new ArrayList<>(this.scores);Creates new list to deep copy nested collection

Profile copy = (Profile) original.clone();Calls clone method to get deep copied object

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Profile {
public:
    string name;
    vector<int> scores;

    Profile(string n, vector<int> s) : name(n), scores(s) {}

    Profile* clone() {
        // Deep copy: create new Profile with copied vector
        vector<int> newScores = scores;
        return new Profile(name, newScores);
    }
};

int main() {
    vector<int> scores = {10, 20};
    Profile original("Alice", scores);
    Profile* copy = original.clone();
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy->scores) cout << x << " ";
    cout << endl;
    copy->scores.push_back(30);
    cout << "After modifying copy scores:" << endl;
    cout << "Original scores: ";
    for (int x : original.scores) cout << x << " ";
    cout << endl;
    cout << "Copy scores: ";
    for (int x : copy->scores) cout << x << " ";
    cout << endl;
    delete copy;
    return 0;
}

Line Notes

Profile* clone() {Defines clone method returning pointer to new deep copied object

vector<int> newScores = scores;Copies vector elements to new vector for deep copy

Profile* copy = original.clone();Calls clone to get deep copy

copy->scores.push_back(30);Modifies copy's vector to verify original is unaffected

class Profile {
    constructor(name, scores) {
        this.name = name;
        this.scores = scores;
    }

    clone() {
        // Deep copy using JSON methods (simple but limited)
        const cloneObj = JSON.parse(JSON.stringify(this));
        return new Profile(cloneObj.name, cloneObj.scores);
    }
}

// Driver code
const original = new Profile('Alice', [10, 20]);
const copy = original.clone();
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);
copy.scores.push(30);
console.log('After modifying copy scores:');
console.log('Original scores:', original.scores);
console.log('Copy scores:', copy.scores);

Line Notes

clone() {Defines clone method using JSON serialization for deep copy

const cloneObj = JSON.parse(JSON.stringify(this));Serializes and deserializes object to create deep copy

return new Profile(cloneObj.name, cloneObj.scores);Returns new Profile instance with copied data

copy.scores.push(30);Modifies copy's array to verify original is unaffected

⏱

Complexity

TimeO(n) where n is size of nested collections

SpaceO(n) additional space for new nested objects

Built-in utilities handle deep copy efficiently and correctly, abstracting complexity.

💡 Using built-in clone methods saves time and reduces bugs compared to manual copying.

Interview Verdict: Accepted and preferred in real-world code for maintainability and correctness

This approach shows mastery of language features and is best practice for cloning.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, implement shallow copy first to show understanding, then deep copy manually or with built-in utilities for correctness.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Shallow Copy)	O(1)	O(1)	No	N/A	Mention only - demonstrates basic concept. Note: C++ vector copy is deep, so shallow copy differs.
2. Better (Manual Deep Copy)	O(n) nested size	O(n)	Possible if recursion too deep	Yes	Code this to show understanding of deep copy
3. Optimal (Built-in Clone/Serialization)	O(n)	O(n)	Depends on implementation	Yes	Mention as best practice in production

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the difference between shallow and deep copy, then explain your approach step-by-step. Practice coding all approaches to be ready for any follow-up questions.

How to Present

Step 1: Clarify the problem and ask if nested objects exist.Step 2: Explain shallow copy and its limitations.Step 3: Implement shallow copy to demonstrate understanding.Step 4: Introduce deep copy and recursive copying of nested objects.Step 5: Show how to use built-in cloning utilities for optimal solution.Step 6: Discuss edge cases and test your code.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of object references, cloning concepts, and ability to implement safe copying. They also check if you can use language features effectively.

Common Follow-ups

• How to handle cyclic references in deep copy? → Use memoization or hash maps to track visited objects.
• Can you implement deep copy for arbitrary objects? → Discuss serialization or reflection-based cloning.

💡 These follow-ups test your deeper understanding of cloning complexities and your ability to handle advanced scenarios.

🔍

Pattern Recognition

When to Use

1. You need to create copies of objects without affecting originals. 2. Objects have nested mutable references. 3. You want to avoid expensive object creation from scratch. 4. You want to clone objects efficiently and safely.

Signature Phrases

clone methoddeep copy vs shallow copyobject copyingprototype pattern

NOT This Pattern When

Factory Pattern - creates new objects but not copies; Builder Pattern - constructs complex objects stepwise.

Similar Problems

Copy Constructor Implementation - similar concept of copying objectsCloneable Interface Usage - language-specific cloningSerialization-based Cloning - alternative deep copy technique

Practice

1. When a class implements an interface and also extends an abstract class, what is the sequence of abstraction enforcement and implementation that occurs during object instantiation?

easy

A. The abstract class constructor runs, but interface methods have no implementation to run.

B. Interface methods are implemented first, then the abstract class constructor runs.

C. The class must implement interface methods before the abstract class constructor runs.

D. The abstract class's constructor runs first, then interface methods are implemented by the class.

Solution

1. Step 1: Understand interface role

   Interfaces declare methods but provide no implementation or constructors.

2. Step 2: Abstract class constructor behavior

   Abstract class constructors run during instantiation to initialize shared state.

3. Step 3: Implementation of interface methods

   The class implementing the interface provides method bodies; no constructor or code runs from interface itself.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Interfaces define contracts only; abstract class constructors run during instantiation.

Hint: Interface methods have no constructor or implementation to run; abstract class constructors always run.

Common Mistakes:

• Thinking interface methods have constructors or code to execute.
• Believing interface implementation order affects constructor execution.
• Confusing interface method implementation with constructor invocation.

2. In the object-oriented design of a Snake and Ladder game, which component is primarily responsible for managing the state transitions of a player's position after a dice roll?

easy

A. The Dice class, since it generates the number that determines movement

B. The Player class, as it holds the current position and updates it directly

C. The Board class, because it contains the snakes and ladders and applies their effects

D. The GameController class, which orchestrates the game flow and updates player positions accordingly

Solution

1. Step 1: Understand the role of Dice

   The Dice only generates a random number; it does not manage state transitions.

2. Step 2: Consider Player class responsibilities

   Player holds position but should not decide how to update it considering snakes or ladders.

3. Step 3: Analyze Board class role

   Board knows snakes and ladders but does not manage player state transitions directly.

4. Step 4: Role of GameController

   GameController coordinates dice roll, queries Board for snakes/ladders, and updates Player position accordingly.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   GameController centralizes state transitions, ensuring separation of concerns.

Hint: GameController orchestrates state changes, not Dice or Player alone [OK]

Common Mistakes:

• Thinking Dice manages player position
• Assuming Player updates position without Board's input
• Believing Board directly changes player state

3. Trace the sequence of events when a client tries to update a private field via a setter method in an encapsulated class.

easy

A. The client directly modifies the private field without any method call

B. The getter method is called first to check the current value before updating

C. The setter method validates the input, updates the private field, then returns control to the client

D. The private field is copied to a public variable which the client modifies

Solution

1. Step 1: Identify encapsulation flow

   Private fields cannot be accessed directly; setters provide controlled access.

2. Step 2: Follow setter method process

   Setter receives input, validates it, updates the private field, then returns control.

3. Step 3: Analyze incorrect options

   The client directly modifies the private field without any method call violates data hiding. The getter method is called first to check the current value before updating misuses getter before setter. The private field is copied to a public variable which the client modifies breaks encapsulation by exposing private data.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Setters control updates with validation, preserving encapsulation.

Hint: Setters validate and update private data, not direct access [OK]

Common Mistakes:

• Assuming direct field access through setters
• Confusing getter and setter roles
• Thinking private data is copied out for modification

4. You are designing a payment processing system that must support new payment methods without changing existing code. Which design approach best aligns with the Open/Closed Principle?

easy

A. Creating a new subclass for each payment method that implements a common payment interface

B. Modifying the existing payment processor class to handle new payment methods directly

C. Adding new conditional branches inside the existing payment processor class for each new payment method

D. Using global variables to switch between payment methods at runtime

Solution

1. Step 1: Identify extension vs modification

   Adding new payment methods should extend behavior without modifying existing classes.

2. Step 2: Evaluate subclassing with common interface

   Creating subclasses for each payment method allows extension by adding new classes, adhering to OCP.

3. Step 3: Why other options fail

   Adding new conditional branches inside the existing payment processor class for each new payment method and modifying existing code violate the 'closed for modification' part. Using global variables to switch between payment methods at runtime uses global state, which is unrelated and error-prone.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Extension via polymorphism, no modification of existing code.

Hint: Extend with new classes, don't modify existing ones [OK]

Common Mistakes:

• Thinking adding conditionals is extension
• Believing modifying existing code is acceptable if tested
• Confusing global state management with OCP

5. What is the time complexity of computing the cost() method when stacking k decorators on a core object using the Decorator Pattern with dynamic behavior injection?

medium

A. O(1) because each decorator adds a fixed cost

B. O(k) because each decorator delegates the call to the next one

C. O(k^2) because each decorator calls all previous decorators recursively

D. O(log k) because decorators form a balanced tree structure

Solution

1. Step 1: Identify call chain length

   Each decorator's cost() calls the wrapped object's cost(), forming a chain of length k.

2. Step 2: Calculate total calls

   Cost computation requires traversing all k decorators once, so time complexity is O(k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each decorator adds constant work, total linear in k [OK]

Hint: Decorator calls chain length equals number of decorators [OK]

Common Mistakes:

• Assuming O(1) because cost is a simple addition
• Mistaking recursive calls as quadratic