Diamond problem in Python - Time & Space Complexity

Time Complexity: Diamond problem

O(n)

Understanding Time Complexity

When working with multiple inheritance in Python, the diamond problem shows how methods are found and called.

We want to understand how the time to find a method grows as the inheritance chain grows.

Scenario Under Consideration

Analyze the time complexity of method lookup in this diamond inheritance example.

class A:
    def method(self):
        return "A"

class B(A):
    def method(self):
        return "B"

class C(A):
    def method(self):
        return "C"

class D(B, C):
    pass

obj = D()
result = obj.method()
    

This code defines a diamond shape inheritance and calls a method on the bottom class.

Identify Repeating Operations

Python looks for the method by checking classes in a specific order.

• Primary operation: Searching classes in the method resolution order (MRO).
• How many times: At most once per class in the method resolution order.

How Execution Grows With Input

As the number of classes in the inheritance chain grows, Python checks each class once in order.

Input Size (number of classes)	Approx. Operations (class checks)
3	3
10	10
100	100

Pattern observation: The number of checks grows directly with the number of classes to search.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a method grows linearly with the number of classes in the inheritance chain.

Common Mistake

[X] Wrong: "Method lookup happens instantly no matter how many classes there are."

[OK] Correct: Python must check each class in order until it finds the method, so more classes mean more checks.

Interview Connect

Understanding how method lookup works helps you reason about multiple inheritance and its costs in real code.

Self-Check

What if we added caching for method lookups? How would that change the time complexity?

Practice

1.

What is the diamond problem in Python's multiple inheritance?

easy

A. A problem where Python cannot find any method in the class hierarchy.

B. A syntax error caused by using multiple inheritance.

C. A situation where a class inherits from two classes that both inherit from the same base class.

D. A situation where a class inherits from only one base class.

Solution

1. Step 1: Understand multiple inheritance structure

   The diamond problem occurs when a class inherits from two classes that share a common ancestor, forming a diamond shape in the inheritance graph.

2. Step 2: Recognize the diamond shape

   This shape causes ambiguity in method resolution because the common base class appears twice in the inheritance path.

3. Final Answer:

   A situation where a class inherits from two classes that both inherit from the same base class. -> Option C

4. Quick Check:

   Diamond problem = multiple inheritance with shared base [OK]

Hint: Diamond problem = shared base class inherited twice [OK]

Common Mistakes:

• Thinking diamond problem is a syntax error
• Confusing single inheritance with diamond problem
• Believing diamond problem means no methods found

2.

Which of the following class definitions correctly shows multiple inheritance that can cause the diamond problem?

class A:
    pass

class B(A):
    pass

class C(A):
    pass

class D(??):
    pass

What should replace ???

easy

A. A, B

B. B, C

C. C, B

D. A, C

Solution

1. Step 1: Identify classes inheriting from A

   Classes B and C both inherit from A, so they form the upper branches of the diamond.

2. Step 2: Define class D inheriting from B and C

   To create the diamond shape, D must inherit from both B and C.

3. Final Answer:

   B, C -> Option B

4. Quick Check:

   Diamond bottom inherits from both branches [OK]

Hint: Diamond bottom class inherits from both intermediate classes [OK]

Common Mistakes:

• Using A directly in D's inheritance
• Swapping order without reason
• Using only one parent class

3.

What will be the output of this code?

class A:
    def greet(self):
        print('Hello from A')

class B(A):
    def greet(self):
        print('Hello from B')

class C(A):
    def greet(self):
        print('Hello from C')

class D(B, C):
    pass

d = D()
d.greet()

medium

A. Hello from B

B. Hello from A

C. Hello from C

D. Hello from D

Solution

1. Step 1: Understand method resolution order (MRO)

   Class D inherits from B and C. Python looks for greet() in D, then B, then C, then A.

2. Step 2: Identify which greet() is called

   D has no greet(), so it calls B's greet() first, printing 'Hello from B'.

3. Final Answer:

   Hello from B -> Option A

4. Quick Check:

   MRO chooses first parent method [OK]

Hint: MRO calls first parent's method in order [OK]

Common Mistakes:

• Assuming C's greet() is called
• Expecting A's greet() to run
• Thinking D has greet() method

4.

Find the error in this code related to the diamond problem:

class A:
    def greet(self):
        print('Hello from A')

class B(A):
    def greet(self):
        print('Hello from B')

class C(A):
    def greet(self):
        print('Hello from C')

class D(B, C):
    def greet(self):
        C.greet(self)

D().greet()

medium

A. Calling C.greet(self) ignores B's greet and breaks MRO.

B. Missing super() call causes infinite recursion.

C. Syntax error in class D definition.

D. No error; code runs fine.

Solution

1. Step 1: Analyze method call in D.greet()

   D.greet() calls C.greet(self) directly, skipping B's greet() and ignoring MRO.

2. Step 2: Understand diamond problem and MRO importance

   By calling C.greet(self) directly, it breaks the expected MRO chain and can cause unexpected behavior.

3. Final Answer:

   Calling C.greet(self) ignores B's greet and breaks MRO. -> Option A

4. Quick Check:

   Direct base class call breaks MRO [OK]

Hint: Avoid direct base class calls; use super() to respect MRO [OK]

Common Mistakes:

• Thinking code has syntax error
• Missing that direct call breaks MRO
• Assuming no error occurs

5.

Given this class structure, what will be the output of D().greet()?

class A:
    def greet(self):
        print('Hello from A')

class B(A):
    def greet(self):
        print('Hello from B')
        super().greet()

class C(A):
    def greet(self):
        print('Hello from C')
        super().greet()

class D(B, C):
    def greet(self):
        print('Hello from D')
        super().greet()

D().greet()

hard

A. Hello from D
Hello from C
Hello from A

B. Hello from D
Hello from C
Hello from B
Hello from A

C. Hello from D
Hello from B
Hello from A

D. Hello from D
Hello from B
Hello from C
Hello from A

Solution

1. Step 1: Determine MRO for class D

   D's MRO is D, B, C, A, object. super() calls follow this order.

2. Step 2: Trace greet() calls

   D.greet() prints 'Hello from D' then calls B.greet(), which prints 'Hello from B' and calls C.greet(), which prints 'Hello from C' and calls A.greet(), which prints 'Hello from A'.

3. Final Answer:

   Hello from D Hello from B Hello from C Hello from A -> Option D

4. Quick Check:

   super() follows MRO chain [OK]

Hint: super() calls follow MRO order in diamond inheritance [OK]

Common Mistakes:

• Ignoring MRO order in super() calls
• Assuming C's greet() runs before B's
• Missing that all greet() methods run