Building blocks of type-safe builders in Kotlin - Time & Space Complexity

Time Complexity: Building blocks of type-safe builders

O(n)

Understanding Time Complexity

When we build type-safe builders in Kotlin, we want to know how the time it takes to run grows as we add more elements or nested blocks.

We ask: How does the work increase when the builder handles more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class HtmlBuilder {
    private val children = mutableListOf()

    fun element(name: String, block: HtmlBuilder.() -> Unit) {
        val childBuilder = HtmlBuilder()
        childBuilder.block()
        children.add("<$name>${childBuilder.render()}</$name>")
    }

    fun render(): String = children.joinToString("")
}

This code builds nested HTML elements by calling element blocks and collecting their rendered strings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling element recursively to build nested elements.
• How many times: Once per element added, plus the join operation over all children when rendering.

How Execution Grows With Input

As you add more elements, the builder calls itself for each nested block and then joins all children strings.

Input Size (n)	Approx. Operations
10	About 10 recursive calls and joining 10 strings
100	About 100 recursive calls and joining 100 strings
1000	About 1000 recursive calls and joining 1000 strings

Pattern observation: The work grows roughly in direct proportion to the number of elements added.

Final Time Complexity

Time Complexity: O(n)

This means the time to build and render grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Because of recursion, the time must grow much faster than the number of elements."

[OK] Correct: Each element calls the builder once, so the total calls equal the number of elements, not more. The recursion depth does not multiply work exponentially.

Interview Connect

Understanding how recursive builders scale helps you explain your code's efficiency clearly and confidently in interviews.

Self-Check

"What if the render method joined children strings inside each recursive call instead of once at the end? How would the time complexity change?"

Practice

1. What is the main purpose of type-safe builders in Kotlin?

easy

A. To create complex objects step-by-step with safety and clarity

B. To write faster loops for collections

C. To handle exceptions automatically

D. To convert data types implicitly

Solution

1. Step 1: Understand the concept of type-safe builders

   Type-safe builders allow building complex objects in a structured and safe way using Kotlin's DSL features.

2. Step 2: Identify the main purpose

   The main goal is to create objects step-by-step with clear rules, avoiding errors and improving readability.

3. Final Answer:

   To create complex objects step-by-step with safety and clarity -> Option A

4. Quick Check:

   Type-safe builders = safe, clear object creation [OK]

Hint: Type-safe builders help build objects safely step-by-step [OK]

Common Mistakes:

• Confusing builders with loops or exception handling
• Thinking they convert data types automatically

2. Which Kotlin syntax correctly defines a type-safe builder function named html that takes a lambda with receiver?

easy

A. fun html(block: (Html) -> Unit) { /*...*/ }

B. fun html(block: () -> Html) { /*...*/ }

C. fun html(block: Html.() -> Unit) { /*...*/ }

D. fun html(block: () -> Unit) { /*...*/ }

Solution

1. Step 1: Identify lambda with receiver syntax

   Type-safe builders use lambdas with receiver, which have the form ReceiverType.() -> ReturnType.

2. Step 2: Match the correct function signature

   The function should accept a lambda with receiver Html and return Unit, so Html.() -> Unit is correct.

3. Final Answer:

   fun html(block: Html.() -> Unit) { /*...*/ } -> Option C

4. Quick Check:

   Lambda with receiver = Html.() -> Unit [OK]

Hint: Look for lambda with receiver syntax ReceiverType.() -> Unit [OK]

Common Mistakes:

• Using regular lambda (Html) -> Unit instead of lambda with receiver
• Omitting the receiver type in the lambda
• Returning Html instead of Unit

3. Given the following Kotlin code, what is the output?

class Html {
    val children = mutableListOf<String>()
    fun body(block: Body.() -> Unit) {
        val body = Body()
        body.block()
        children.addAll(body.contents)
    }
    override fun toString() = children.joinToString(", ")
}

class Body {
    val contents = mutableListOf<String>()
    fun p(text: String) {
        contents.add("
$text
")
    }
}

fun html(block: Html.() -> Unit): Html {
    val html = Html()
    html.block()
    return html
}

fun main() {
    val result = html {
        body {
            p("Hello")
            p("World")
        }
    }
    println(result)
}

medium

A. Hello, World

B. <p>Hello</p>, <p>World</p>

C. <body><p>Hello</p><p>World</p></body>

D. Compilation error

Solution

1. Step 1: Understand the builder structure

   The html function creates an Html object, calls body which creates a Body object, then calls p twice adding <p>Hello</p> and <p>World</p> to Body's contents.

2. Step 2: Check how children are collected and printed

   The Html object's children list gets Body's contents added, then toString() joins them with ", ". So output is "<p>Hello</p>, <p>World</p>".

3. Final Answer:

   <p>Hello</p>, <p>World</p> -> Option B

4. Quick Check:

   Children list joined = <p>Hello</p>, <p>World</p> [OK]

Hint: Look for toString join of children list for output [OK]

Common Mistakes:

• Assuming HTML tags are printed as is without escaping
• Expecting full HTML tags like <body> in output
• Thinking code causes compilation error

4. What is the error in this Kotlin builder code snippet?

class Html {
    fun body(block: Body.() -> Unit) {
        val body = Body()
        block()
    }
}

class Body {
    fun p(text: String) { /*...*/ }
}

fun main() {
    val html = Html()
    html.body {
        p("Hello")
    }
}

medium

A. The lambda is called without receiver, so 'p' is unresolved

B. Body class is missing a constructor

C. Html class should inherit from Body

D. The 'body' function should return a value

Solution

1. Step 1: Check how the lambda is called inside body()

   The lambda block is called as block() without receiver, so inside the lambda 'p' is not recognized.

2. Step 2: Identify correct lambda invocation

   It should be called as body.block() to set the receiver to the Body instance, allowing 'p' to be resolved.

3. Final Answer:

   The lambda is called without receiver, so 'p' is unresolved -> Option A

4. Quick Check:

   Lambda call without receiver = unresolved 'p' [OK]

Hint: Call lambda with receiver: use receiver.lambda() syntax [OK]

Common Mistakes:

• Calling lambda without receiver inside builder
• Assuming inheritance fixes builder scope
• Expecting return value from builder function

5. How can you extend a type-safe builder to support nested elements, for example adding a div inside body, while keeping type safety?

hard

A. Use a global div function outside the builder classes

B. Add a div property of type String to Body

C. Make Body inherit from Div

D. Define a div function inside Body that takes a lambda with receiver of a new Div class

Solution

1. Step 1: Understand nested builder pattern

   To support nested elements, define functions inside builder classes that accept lambdas with receivers of nested element classes.

2. Step 2: Apply to 'div' inside 'body'

   Inside Body, define a div function taking Div.() -> Unit lambda, creating a Div instance and applying the lambda to it.

3. Final Answer:

   Define a div function inside Body that takes a lambda with receiver of a new Div class -> Option D

4. Quick Check:

   Nested builders = functions with lambdas with receiver [OK]

Hint: Nested builders use functions with lambdas with receiver inside classes [OK]

Common Mistakes:

• Using simple properties instead of nested builder functions
• Trying inheritance instead of composition
• Defining builder functions outside the class scope