Composite pattern in LLD - System Design Exercise

Design: Composite Pattern Implementation

Focus on the design and implementation of the Composite pattern structure and its interaction. Out of scope are specific UI rendering or persistence mechanisms.

Functional Requirements

FR1: Design a system to represent part-whole hierarchies where individual objects and compositions of objects are treated uniformly.

FR2: Support operations that can be performed on both single objects and groups of objects.

FR3: Allow clients to interact with objects and compositions without knowing their exact types.

FR4: Enable adding or removing child components dynamically.

Non-Functional Requirements

NFR1: The system should be easy to extend with new component types.

NFR2: Operations should be performed recursively on composite objects.

NFR3: The design should minimize code duplication between leaf and composite objects.

NFR4: The system should handle hierarchies of arbitrary depth.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Component interface or abstract class defining common operations

Leaf class representing individual objects

Composite class representing groups of components

Client code interacting with components through the common interface

Design Patterns

Composite pattern for part-whole hierarchies

Iterator pattern for traversing child components

Visitor pattern for operations on components (optional extension)

Reference Architecture

Client
  |
  v
Component Interface
  /       \
Leaf     Composite
           |
           +-- Child Components (List of Component)

Components

Component Interface

Abstract class or interface

Defines common operations for both leaf and composite objects.

Leaf

Concrete class

Represents individual objects with no children.

Composite

Concrete class

Represents objects that have children and implements operations recursively.

Client

Any programming environment

Interacts with components through the common interface without knowing their concrete types.

Request Flow

1. Client calls an operation on a Component reference.

2. If the Component is a Leaf, it performs the operation directly.

3. If the Component is a Composite, it performs the operation and recursively calls the same operation on its child components.

4. Results from child components can be aggregated if needed.

5. Client receives the result without needing to know if it came from a Leaf or Composite.

Database Schema

Not applicable as this is a design pattern focused on object structure rather than data storage.

Scaling Discussion

Bottlenecks

Deep hierarchies may cause stack overflow in recursive operations.

Large numbers of child components can lead to performance issues during recursive traversal.

Modifying the hierarchy concurrently can cause consistency problems.

Solutions

Use iterative traversal with explicit stacks to avoid deep recursion issues.

Implement caching or memoization for expensive operations on composites.

Use thread-safe data structures or synchronization mechanisms when modifying the hierarchy concurrently.

Interview Tips

Time: Spend 10 minutes explaining the problem and requirements, 20 minutes designing the pattern with diagrams and code sketches, and 15 minutes discussing scaling and extensions.

Explain the need for treating individual and composite objects uniformly.

Describe the roles of Component, Leaf, and Composite classes.

Show how recursive operations work in the Composite.

Discuss how the pattern simplifies client code.

Mention potential issues with deep hierarchies and concurrency.

Suggest extensions like adding iterators or visitors.

Practice

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

easy

A. To create a single instance of a class

B. To separate interface from implementation

C. To provide a way to access elements of a collection sequentially

D. To treat individual objects and compositions of objects uniformly

Solution

1. Step 1: Understand the Composite pattern goal

   The Composite pattern allows treating individual objects and groups of objects the same way.

2. Step 2: Compare with other design patterns

   Other options describe different patterns: Singleton (A), Iterator (D), Bridge (B).

3. Final Answer:

   To treat individual objects and compositions of objects uniformly -> Option D

4. Quick Check:

   Composite pattern = treat objects uniformly [OK]

Hint: Composite = treat single and group objects the same [OK]

Common Mistakes:

• Confusing Composite with Singleton pattern
• Thinking Composite only manages single objects
• Mixing Composite with Iterator or Bridge patterns

2. Which of the following is the correct way to declare a composite interface method in a class diagram for the Composite pattern?

easy

A. int calculateSum(int a, int b);

B. void add(Component component);

C. String toString();

D. boolean equals(Object obj);

Solution

1. Step 1: Identify typical Composite interface methods

   Composite pattern usually includes methods like add(), remove(), and getChild() to manage children.

2. Step 2: Match method signature to Composite pattern

   Only void add(Component component); fits the pattern's purpose of managing child components.

3. Final Answer:

   void add(Component component); -> Option B

4. Quick Check:

   Composite interface method = add(Component) [OK]

Hint: Composite interface manages children with add/remove methods [OK]

Common Mistakes:

• Choosing unrelated method signatures
• Confusing standard Object methods with Composite methods
• Ignoring the need to manage child components

3. Given the following code snippet in a Composite pattern implementation, what will be the output?

class Component:
  def operation(self):
    pass

class Leaf(Component):
  def operation(self):
    return "Leaf"

class Composite(Component):
  def __init__(self):
    self.children = []
  def add(self, component):
    self.children.append(component)
  def operation(self):
    results = []
    for child in self.children:
      results.append(child.operation())
    return "Composite(" + ", ".join(results) + ")"

leaf1 = Leaf()
leaf2 = Leaf()
composite = Composite()
composite.add(leaf1)
composite.add(leaf2)
print(composite.operation())

medium

A. Composite(Leaf, Leaf)

B. Leaf, Leaf

C. Composite()

D. Leaf

Solution

1. Step 1: Understand Leaf operation output

   Each Leaf's operation returns the string "Leaf".

2. Step 2: Understand Composite operation output

   Composite calls operation on each child and joins results with commas inside "Composite(...)".

3. Final Answer:

   Composite(Leaf, Leaf) -> Option A

4. Quick Check:

   Composite operation = Composite(Leaf, Leaf) [OK]

Hint: Composite operation joins child operations in parentheses [OK]

Common Mistakes:

• Expecting just 'Leaf' output
• Ignoring the Composite wrapper in output
• Confusing list join syntax

4. In the following Composite pattern code, what is the main error?

class Component:
  def operation(self):
    pass

class Leaf(Component):
  def operation(self):
    return "Leaf"

class Composite(Component):
  def __init__(self):
    self.children = []
  def add(self, component):
    self.children.append(component)
  def operation(self):
    results = []
    for child in self.children:
      child.operation()
    return "Composite(" + ", ".join(results) + ")"

medium

A. The add method does not check component type

B. The Composite class does not initialize children list

C. The operation method does not collect child results

D. The Leaf class does not inherit from Component

Solution

1. Step 1: Analyze operation method in Composite

   The loop calls child.operation() but does not append results to the list.

2. Step 2: Identify missing result collection

   Without appending, results remains empty, causing incorrect output.

3. Final Answer:

   The operation method does not collect child results -> Option C

4. Quick Check:

   Missing append in loop = operation method error [OK]

Hint: Check if child results are collected in operation method [OK]

Common Mistakes:

• Ignoring missing append to results list
• Thinking add method type check is mandatory
• Assuming inheritance error without evidence

5. You are designing a UI framework using the Composite pattern. You want to add a feature to calculate the total number of visible elements in a nested component tree. Which approach best fits the Composite pattern principles?

hard

A. Add a countVisible() method to the Component interface, implemented by Leaf and Composite classes

B. Use a global counter variable updated externally during rendering

C. Only count visible elements in Leaf nodes, ignoring Composite nodes

D. Traverse the tree manually outside the classes to count visible elements

Solution

1. Step 1: Apply Composite pattern principle of uniformity

   Adding countVisible() to Component interface lets all nodes handle counting uniformly.

2. Step 2: Implement counting in Leaf and Composite

   Leaf returns 1 if visible, 0 otherwise; Composite sums counts from children.

3. Final Answer:

   Add a countVisible() method to the Component interface, implemented by Leaf and Composite classes -> Option A

4. Quick Check:

   Uniform method in Component = best Composite design [OK]

Hint: Add counting method to Component interface for uniformity [OK]

Common Mistakes:

• Using external counters breaking encapsulation
• Counting only leaves ignoring composites
• Manual traversal outside object methods