Interface satisfaction in Go - Time & Space Complexity

Time Complexity: Interface satisfaction

O(n)

Understanding Time Complexity

When working with interfaces in Go, it's important to understand how the program checks if a type fits an interface.

We want to see how the time needed to confirm this fit changes as the program runs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

import "fmt"

type Speaker interface {
    Speak() string
}

type Person struct {
    Name string
}

func (p Person) Speak() string {
    return "Hello, " + p.Name
}

func main() {
    var s Speaker
    p := Person{Name: "Alice"}
    s = p // interface satisfaction happens here
    fmt.Println(s.Speak())
}

This code checks if a Person type satisfies the Speaker interface by assigning it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The program checks the method set of the Person type against the Speaker interface methods.
• How many times: This check happens once at assignment time for this example.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (number of interface methods)	Approx. Operations
1	1 method check
5	5 method checks
10	10 method checks

Pattern observation: The time to check grows linearly with the number of methods in the interface.

Final Time Complexity

Time Complexity: O(n)

This means the time to confirm interface satisfaction grows directly with the number of methods the interface has.

Common Mistake

[X] Wrong: "Checking if a type satisfies an interface is instant and does not depend on the interface size."

[OK] Correct: The program must check each method in the interface against the type's methods, so more methods mean more checks.

Interview Connect

Understanding how interface satisfaction works helps you reason about Go's type system and performance in real programs.

Self-Check

"What if the interface had embedded interfaces? How would that affect the time complexity of satisfaction checks?"

Practice

1. Which statement best describes how a type satisfies an interface in Go?

easy

A. A type satisfies an interface by implementing all the methods declared in the interface.

B. A type satisfies an interface only if it explicitly declares it implements the interface.

C. A type satisfies an interface by embedding the interface in its struct definition.

D. A type satisfies an interface by having the same name as the interface.

Solution

1. Step 1: Understand interface satisfaction in Go

   In Go, a type satisfies an interface if it implements all the methods declared in that interface.

2. Step 2: Check explicit declaration requirement

   Go does not require explicit declaration; satisfaction is implicit by method implementation.

3. Final Answer:

   A type satisfies an interface by implementing all the methods declared in the interface. -> Option A

4. Quick Check:

   Interface satisfaction = implicit method implementation [OK]

Hint: Remember: Implement all methods, no explicit declaration needed [OK]

Common Mistakes:

• Thinking explicit declaration is required
• Confusing embedding with satisfaction
• Matching names instead of methods

2. Which of the following Go code snippets correctly shows a type satisfying an interface Speaker with method Speak()?

easy

A. type Speaker interface { Speak() string }
type Dog struct {}
func (d Dog) speak() string { return "Woof" }

B. type Speaker interface { Speak() string }
type Dog struct {}
func (d Dog) Speak() string { return "Woof" }

C. type Speaker interface { Speak() string }
type Dog struct {}
func Speak(d Dog) string { return "Woof" }

D. type Speaker interface { Speak() string }
type Dog struct {}
func (d *Dog) Speak() int { return 1 }

Solution

1. Step 1: Check method signature and receiver

   type Speaker interface { Speak() string } type Dog struct {} func (d Dog) Speak() string { return "Woof" } defines Speak() with correct receiver (d Dog) and return type string.

2. Step 2: Verify method name and return type match interface

   type Speaker interface { Speak() string } type Dog struct {} func (d Dog) speak() string { return "Woof" } has lowercase speak(), so it does not satisfy interface. type Speaker interface { Speak() string } type Dog struct {} func Speak(d Dog) string { return "Woof" } defines a function, not a method. type Speaker interface { Speak() string } type Dog struct {} func (d *Dog) Speak() int { return 1 } has wrong return type int.

3. Final Answer:

   type Speaker interface { Speak() string } type Dog struct {} func (d Dog) Speak() string { return "Woof" } -> Option B

4. Quick Check:

   Method name and signature must match exactly [OK]

Hint: Method name and signature must match interface exactly [OK]

Common Mistakes:

• Using lowercase method names
• Defining functions instead of methods
• Mismatching return types

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

package main
import "fmt"

type Reader interface {
  Read() string
}

type File struct {}
func (f File) Read() string {
  return "file content"
}

func printContent(r Reader) {
  fmt.Println(r.Read())
}

func main() {
  f := File{}
  printContent(f)
}

medium

A. No output

B. Compilation error: File does not satisfy Reader

C. file content

D. Runtime panic

Solution

1. Step 1: Check if File satisfies Reader interface

   File has method Read() string, so it satisfies Reader.

2. Step 2: Trace function call and output

   In main, f is passed to printContent, which calls Read() and prints "file content".

3. Final Answer:

   file content -> Option C

4. Quick Check:

   Interface satisfied, method called, prints string [OK]

Hint: Check method presence to confirm interface satisfaction [OK]

Common Mistakes:

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

4. Identify the error in the following Go code that prevents Car from satisfying the Vehicle interface:

package main
import "fmt"

type Vehicle interface {
  Drive()
}

type Car struct {}
func (c *Car) Drive() {
  fmt.Println("Driving")
}

func main() {
  var v Vehicle
  c := Car{}
  v = c
  v.Drive()
}

medium

A. Car does not satisfy Vehicle because Drive has pointer receiver but v is assigned a value.

B. Drive method has wrong return type.

C. Vehicle interface requires Drive with parameters.

D. No error, code runs fine.

Solution

1. Step 1: Check method receiver type

   Drive is defined with pointer receiver (*Car), so only *Car satisfies Vehicle, not Car value.

2. Step 2: Check assignment in main

   Variable v is assigned c which is a value, not pointer, causing mismatch.

3. Final Answer:

   Car does not satisfy Vehicle because Drive has pointer receiver but v is assigned a value. -> Option A

4. Quick Check:

   Pointer receiver methods require pointer type for interface satisfaction [OK]

Hint: Pointer receiver methods need pointer type to satisfy interface [OK]

Common Mistakes:

• Assigning value instead of pointer to interface
• Ignoring receiver type in method
• Assuming method signature mismatch

5. Given the interface and types below, which assignment will cause a compile-time error due to interface satisfaction rules?

type Writer interface {
  Write(data string) error
}

type Logger struct {}
func (l Logger) Write(data string) error {
  return nil
}

type FileWriter struct {}
func (f *FileWriter) Write(data string) error {
  return nil
}

var w Writer

// Which assignment is invalid?
// A) w = Logger{}
// B) w = &Logger{}
// C) w = FileWriter{}
// D) w = &FileWriter{}

hard

A. w = &FileWriter{}

B. w = &Logger{}

C. w = Logger{}

D. w = FileWriter{}

Solution

1. Step 1: Analyze Logger methods

   Logger has Write with value receiver, so both Logger and *Logger satisfy Writer.

2. Step 2: Analyze FileWriter methods

   FileWriter has Write with pointer receiver, so only *FileWriter satisfies Writer, not FileWriter value.

3. Step 3: Check assignments

   Assignment C tries to assign FileWriter{} value to Writer, which is invalid.

4. Final Answer:

   w = FileWriter{} causes compile-time error due to missing method on value receiver. -> Option D

5. Quick Check:

   Pointer receiver methods require pointer type for interface [OK]

Hint: Pointer receiver methods need pointer type for interface satisfaction [OK]

Common Mistakes:

• Assigning value type when method has pointer receiver
• Assuming pointer and value types are interchangeable
• Ignoring method receiver type