Implementing interfaces in Java - Time & Space Complexity

Time Complexity: Implementing interfaces

O(n)

Understanding Time Complexity

When we implement interfaces in Java, we write methods that follow a contract. It's important to see how the time it takes to run these methods changes as the input grows.

We want to know: how does the running time grow when the input size increases in these implementations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public interface Printer {
    void printAll(String[] messages);
}

public class SimplePrinter implements Printer {
    public void printAll(String[] messages) {
        for (String msg : messages) {
            System.out.println(msg);
        }
    }
}
    

This code defines an interface with a method to print all messages, and a class that implements it by printing each message one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array of messages to print each one.
• How many times: Once for each message in the input array.

How Execution Grows With Input

As the number of messages grows, the time to print them grows too, because each message is handled one by one.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: The time grows directly with the number of messages; doubling messages doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the printAll method grows in a straight line with the number of messages.

Common Mistake

[X] Wrong: "Implementing an interface method always takes constant time because it's just one method call."

[OK] Correct: The method can do work that depends on input size, like looping through an array, so time can grow with input.

Interview Connect

Understanding how your interface methods scale with input size shows you can write efficient code and reason about performance, a key skill in real projects.

Self-Check

"What if the printAll method called another method inside the loop that itself loops over the messages? How would the time complexity change?"

Practice

1. What keyword does a Java class use to follow an interface?

easy

A. uses

B. extends

C. inherits

D. implements

Solution

1. Step 1: Understand Java class and interface relationship

   In Java, a class follows an interface by using a specific keyword to promise it will provide all methods declared in the interface.

2. Step 2: Identify the correct keyword

   The keyword to make a class follow an interface is implements, not extends which is for classes inheriting other classes.

3. Final Answer:

   implements -> Option D

4. Quick Check:

   Class follows interface = implements [OK]

Hint: Remember: classes use implements for interfaces, extends for classes [OK]

Common Mistakes:

• Using extends instead of implements for interfaces
• Confusing inherits keyword which doesn't exist in Java
• Using uses keyword which is invalid

2. Which of the following is the correct syntax to declare a class Car that implements interface Vehicle?

easy

A. class Car extends Vehicle {}

B. class Car implements Vehicle {}

C. interface Car implements Vehicle {}

D. class Car uses Vehicle {}

Solution

1. Step 1: Identify class and interface keywords

   A class is declared with class, and interfaces with interface. Here, Car is a class, Vehicle is an interface.

2. Step 2: Use correct syntax for implementing interface

   The class Car must use implements keyword to follow Vehicle interface. So class Car implements Vehicle {} is correct.

3. Final Answer:

   class Car implements Vehicle {} -> Option B

4. Quick Check:

   Class + implements + Interface = correct syntax [OK]

Hint: Class implements interface with 'implements' keyword [OK]

Common Mistakes:

• Using extends instead of implements for interfaces
• Declaring class as interface
• Using invalid keyword uses

3. What will be the output of this code?

interface Printer {
    void print();
}

class Document implements Printer {
    public void print() {
        System.out.println("Printing document");
    }
}

public class Main {
    public static void main(String[] args) {
        Printer p = new Document();
        p.print();
    }
}

medium

A. Printing document

B. Compilation error: print() not implemented

C. Runtime error

D. No output

Solution

1. Step 1: Check if interface method is implemented

   The interface Printer declares method print(). The class Document implements Printer and provides public void print() method, so no error.

2. Step 2: Trace main method execution

   Main creates Printer reference p to new Document object and calls p.print(). This calls Document's print() which prints "Printing document".

3. Final Answer:

   Printing document -> Option A

4. Quick Check:

   Implemented method runs and prints output [OK]

Hint: Implemented interface methods run normally when called [OK]

Common Mistakes:

• Forgetting to make print() public causes compile error
• Assuming interface methods run automatically without implementation
• Confusing runtime error with compile error

4. Identify the error in this code:

interface Animal {
    void sound();
}

class Dog implements Animal {
    void sound() {
        System.out.println("Bark");
    }
}

medium

A. No error, code is correct

B. Dog should extend Animal, not implement

C. Method sound() must be public in Dog class

D. Interface Animal cannot have methods

Solution

1. Step 1: Check method visibility in interface implementation

   Interface methods are implicitly public. When implementing, the method must be declared public in the class.

2. Step 2: Identify method declaration in Dog class

   Dog's sound() method has default (package-private) visibility, missing public keyword, causing compile error.

3. Final Answer:

   Method sound() must be public in Dog class -> Option C

4. Quick Check:

   Interface methods require public implementation [OK]

Hint: Interface methods must be public in implementing class [OK]

Common Mistakes:

• Omitting public keyword on implemented methods
• Using extends instead of implements for interfaces
• Thinking interface methods can be private

5. Given interface Calculator with methods add(int a, int b) and subtract(int a, int b), which class correctly implements it to return the sum and difference respectively?

hard

A. class Calc implements Calculator {
public int add(int a, int b) { return a + b; }
public int subtract(int a, int b) { return a - b; }
}

B. class Calc implements Calculator {
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
}

C. class Calc extends Calculator {
public int add(int a, int b) { return a + b; }
public int subtract(int a, int b) { return a - b; }
}

D. class Calc implements Calculator {
public void add(int a, int b) { System.out.println(a + b); }
public void subtract(int a, int b) { System.out.println(a - b); }
}

Solution

1. Step 1: Check method signatures and visibility

   Interface methods are public and return int. So implementing methods must be public and return int with same parameters.

2. Step 2: Analyze each option

   class Calc implements Calculator { public int add(int a, int b) { return a + b; } public int subtract(int a, int b) { return a - b; } } matches signatures exactly with public int return type. class Calc implements Calculator { int add(int a, int b) { return a + b; } int subtract(int a, int b) { return a - b; } } misses public keyword. class Calc extends Calculator { public int add(int a, int b) { return a + b; } public int subtract(int a, int b) { return a - b; } } uses extends which is invalid for interfaces. class Calc implements Calculator { public void add(int a, int b) { System.out.println(a + b); } public void subtract(int a, int b) { System.out.println(a - b); } } changes return type to void, which is incorrect.

3. Final Answer:

   class Calc implements Calculator { public int add(int a, int b) { return a + b; } public int subtract(int a, int b) { return a - b; } } -> Option A

4. Quick Check:

   Match method signatures exactly with public and return type [OK]

Hint: Implemented methods must match interface signatures exactly [OK]

Common Mistakes:

• Omitting public keyword on methods
• Using extends instead of implements for interfaces
• Changing return types or parameters