Implementing interfaces in Go - Time & Space Complexity

Time Complexity: Implementing interfaces

O(n)

Understanding Time Complexity

When we implement interfaces in Go, we want to know how the program's running time changes as we use these interfaces more.

We ask: How does the time to call interface methods grow when we have more data or calls?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

import "fmt"

type Speaker interface {
    Speak()
}

type Person struct {
    name string
}

func (p Person) Speak() {
    fmt.Println("Hello, my name is", p.name)
}

func greetAll(speakers []Speaker) {
    for _, speaker := range speakers {
        speaker.Speak()
    }
}

func main() {
    people := []Person{{"Alice"}, {"Bob"}, {"Carol"}}
    var speakers []Speaker
    for _, p := range people {
        speakers = append(speakers, p)
    }
    greetAll(speakers)
}
    

This code defines an interface and calls its method on a list of objects implementing it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over the slice of speakers and calling the Speak() method on each.
• How many times: Once for each element in the speakers slice, so as many times as the number of speakers.

How Execution Grows With Input

As the number of speakers grows, the number of method calls grows the same way.

Input Size (n)	Approx. Operations
10	10 calls to Speak()
100	100 calls to Speak()
1000	1000 calls to Speak()

Pattern observation: The work grows directly with the number of speakers; double the speakers, double the calls.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of interface objects we call.

Common Mistake

[X] Wrong: "Calling methods through interfaces is slower and adds extra hidden loops that increase time complexity."

[OK] Correct: Calling an interface method adds a small fixed cost per call but does not add loops or change how many times the method runs. The main time depends on how many calls we make, not on the interface itself.

Interview Connect

Understanding how interface method calls scale helps you write clear and efficient Go code. It shows you can reason about performance while using Go's powerful features.

Self-Check

"What if we changed the slice of interface objects to a slice of concrete types and called methods directly? How would the time complexity change?"

Practice

1. What does it mean for a type in Go to implement an interface?

easy

A. The type can only have one method.

B. The type inherits from the interface.

C. The type must be explicitly declared as implementing the interface.

D. The type has all the methods declared in the interface.

Solution

1. Step 1: Understand interface implementation in Go

   In Go, a type implements an interface by having all the methods the interface declares.

2. Step 2: Compare options with Go's rules

   Go does not use inheritance or explicit declarations for interfaces; it uses method sets.

3. Final Answer:

   The type has all the methods declared in the interface. -> Option D

4. Quick Check:

   Interface implementation = method set match [OK]

Hint: Check if all interface methods exist in the type [OK]

Common Mistakes:

• Thinking Go uses inheritance for interfaces
• Believing explicit declaration is needed
• Confusing interfaces with structs

2. Which of the following is the correct way to declare that a type implements an interface in Go?

easy

A. type MyType struct implements MyInterface {}

B. type MyType struct { MyInterface }

C. No explicit declaration needed; implement all interface methods

D. func (m MyType) implements() MyInterface {}

Solution

1. Step 1: Recall Go interface implementation syntax

   Go does not require explicit declarations; a type implements an interface by having all its methods.

2. Step 2: Analyze each option

   Options A, B, and D show invalid or non-Go syntax; only C correctly states Go's implicit implementation.

3. Final Answer:

   No explicit declaration needed; implement all interface methods -> Option C

4. Quick Check:

   Implicit implementation = No explicit declaration needed; implement all interface methods [OK]

Hint: Remember: Go uses implicit interface implementation [OK]

Common Mistakes:

• Trying to declare implementation explicitly
• Using inheritance syntax from other languages
• Adding interface as a struct field

3. What will be the output of the following Go code?

package main
import "fmt"
type Speaker interface {
    Speak() string
}
type Dog struct {}
func (d Dog) Speak() string {
    return "Woof!"
}
func saySomething(s Speaker) {
    fmt.Println(s.Speak())
}
func main() {
    var d Dog
    saySomething(d)
}

medium

A. Woof!

B. Compilation error: Dog does not implement Speaker

C. Runtime error

D. No output

Solution

1. Step 1: Check if Dog implements Speaker

   Dog has a method Speak() string, so it implements Speaker interface.

2. Step 2: Trace the function call saySomething(d)

   saySomething calls s.Speak(), which returns "Woof!" and prints it.

3. Final Answer:

   Woof! -> Option A

4. Quick Check:

   Interface method call prints "Woof!" [OK]

Hint: Check if method signatures match interface exactly [OK]

Common Mistakes:

• Assuming explicit declaration is needed
• Confusing method receiver types
• Expecting runtime errors without reason

4. Identify the error in this Go code that tries to implement an interface:

package main
import "fmt"
type Runner interface {
    Run()
}
type Person struct {}
func (p *Person) Run() {
    fmt.Println("Running")
}
func main() {
    var r Runner
    p := Person{}
    r = p
    r.Run()
}

medium

A. Missing Run() method in Person

B. Cannot assign Person value to Runner interface because Run() has pointer receiver

C. Interface Runner must have a return type

D. No error, code runs fine

Solution

1. Step 1: Check method receiver type

   Run() is defined with pointer receiver (*Person), so only *Person implements Runner.

2. Step 2: Analyze assignment r = p

   Variable p is a Person value, not *Person pointer, so it does not implement Runner.

3. Final Answer:

   Cannot assign Person value to Runner interface because Run() has pointer receiver -> Option B

4. Quick Check:

   Pointer receiver method requires pointer type [OK]

Hint: Match method receiver type with assigned variable type [OK]

Common Mistakes:

• Ignoring pointer vs value receiver difference
• Assuming interface methods must return values
• Thinking interface assignment always works

5. Given these interfaces and types, which assignment is valid in Go?

type Reader interface {
    Read() string
}
type Writer interface {
    Write(string)
}
type ReadWriter interface {
    Reader
    Writer
}
type File struct {}
func (f *File) Read() string {
    return "data"
}
func (f *File) Write(s string) {
    // write data
}
func main() {
    var rw ReadWriter
    var f File
    // Which assignment is valid?
}

hard

A. rw = &f

B. rw = f

C. rw = File{} (without methods)

D. rw = nil

Solution

1. Step 1: Check if File implements ReadWriter

   File has Read() and Write(string) with pointer receivers (*File), so only *File implements ReadWriter; File value does not.

2. Step 2: Analyze assignment options

   rw = &f is valid (&f is *File). rw = f fails (File doesn't implement). C invalid. rw = nil compiles but doesn't hold usable ReadWriter.

3. Final Answer:

   rw = &f -> Option A

4. Quick Check:

   Pointer receiver requires pointer type [OK]

Hint: Pointer receiver methods mean only pointer type implements interface [OK]

Common Mistakes:

• Thinking value type implements pointer receiver interface
• Assigning nil to interface without initialization
• Confusing interface embedding with inheritance