Category: Kotlin coding test

Hello! In this post, we will discuss an algorithm problem that can be solved using Kotlin.
The topic is Finding the Minimum Cost. This problem can be presented in various forms and is a common type seen in coding tests.
In this article, I will explain a systematic problem-solving process that includes problem description, algorithm design, Kotlin code implementation, examples, and test cases.

Problem Description

There is a directed graph with N vertices and M edges. Each edge is irreversible and has a specific cost assigned.
Your task is to find the minimum cost from a specific starting vertex to the target vertex.
The edges can be connected in various ways, and there may be multiple paths leading to the same vertex.

Input Format:

• The first line contains the number of vertices N and the number of edges M.
• From the second line to the M-th line, edge information is given: starting vertex A, ending vertex B, cost C.
• The last line contains the starting vertex and the target vertex.

Output Format:

• Output the minimum cost to reach the target vertex from the starting vertex. If it is unreachable, output -1.

Example Input

5 6
1 2 2
1 3 3
2 4 1
3 4 4
2 5 5
4 5 1
1 5

Example Output

8

Problem Solving Approach

This problem is a shortest path problem and can be effectively solved using Dijkstra’s algorithm. Dijkstra’s algorithm
shows excellent performance in finding the shortest path from a specific starting vertex to all other vertices in a graph.
In this section, we will take a closer look at the overview of Dijkstra’s algorithm and how to implement it in Kotlin.

Overview of Dijkstra’s Algorithm

Dijkstra’s algorithm operates based on the following principles:

• Initialize the shortest path from the starting vertex to all other vertices. Set the distance from the starting vertex to 0, and other vertices to infinity.
• Use a priority queue to repeatedly select the vertex with the shortest path discovered so far.
• Update distances for adjacent vertices based on the shortest path criteria.
• Repeat this process until all vertices are selected or all remaining vertices have distances of infinity.

Through this process, we can ultimately find the minimum cost from the starting vertex to the target vertex.

Kotlin Code Implementation

Now let’s implement the Dijkstra’s algorithm in Kotlin to solve the problem.
We will first import the necessary libraries, process the input, and then implement the algorithm.

import java.util.PriorityQueue

data class Edge(val to: Int, val cost: Int)

fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
    val distance = IntArray(n + 1) { Int.MAX_VALUE }
    val priorityQueue = PriorityQueue>(compareBy { it.first })
    
    distance[start] = 0
    priorityQueue.add(0 to start)

    while (priorityQueue.isNotEmpty()) {
        val (currentDist, currentNode) = priorityQueue.poll()
        
        if (currentDist > distance[currentNode]) continue

        for (edge in edges[currentNode]) {
            val newDist = currentDist + edge.cost
            
            if (newDist < distance[edge.to]) {
                distance[edge.to] = newDist
                priorityQueue.add(newDist to edge.to)
            }
        }
    }

    return distance
}

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val edges = List(n + 1) { mutableListOf() }

    for (i in 1..m) {
        val (a, b, cost) = readLine()!!.split(" ").map { it.toInt() }
        edges[a].add(Edge(b, cost))
    }

    val (start, end) = readLine()!!.split(" ").map { it.toInt() }
    val distances = dijkstra(n, edges, start)

    println(if (distances[end] == Int.MAX_VALUE) -1 else distances[end])
}

Code Explanation

The above code is a Kotlin program that uses Dijkstra’s algorithm to solve the problem. Let’s take a look at the main components of the code.

• Edge Data Class: A data class that represents the edges of the graph. Each edge contains information about the destination vertex and the cost.
• dijkstra Function: A function that implements Dijkstra’s algorithm. It takes the number of vertices n, the list of edges edges, and the starting vertex start as inputs.
  It initializes the distance array to store the shortest path information and uses a priority queue to search for paths.
• main Function: Handles input and calls the dijkstra function. Finally, it outputs the minimum cost to the target vertex.
  If it cannot be reached, -1 is printed.

Test Cases

Let’s create some test cases to verify the functionality of the code.
It’s important to check the performance and accuracy of the code by considering various scenarios.

Test Case 1

Input:
5 6
1 2 2
1 3 3
2 4 1
3 4 4
2 5 5
4 5 1
1 5

Output:
8

Test Case 2

Input:
3 2
1 2 2
1 3 4
2 3 5
1 3

Output:
4

Test Case 3

Input:
4 3
1 2 10
2 3 5
3 4 10
1 4

Output:
-1

Conclusion

In this post, we learned about how to solve the minimum cost finding problem using Kotlin.
We explained how to efficiently find the shortest path in a graph using Dijkstra’s algorithm,
implemented it in Kotlin, and verified the code’s functionality with several test cases.
It was an opportunity to deepen our understanding of algorithms and Kotlin programming.
I will return with useful algorithm problems and solutions in the future.
Thank you!

Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along with explanations of the topic.

Problem Definition

The problem is to find the lowest common ancestor of node A and node B when a tree structure is given. The Lowest Common Ancestor is the deepest ancestor among the ancestors of nodes A and B. For example, consider the tree structure shown below.

            1
           / \
          2   3
         / \   \
        4   5   6
       /
      7

In this case, the lowest common ancestor of node 4 and node 5 is node 2. Additionally, the lowest common ancestor of node 4 and node 6 is node 1.

Input

• First line: The number of nodes N in the tree (1 ≤ N ≤ 20,000)
• From the second line to the N-1th line: Two integers a, b are given, indicating that a is the parent of b.
• Last line: Two integers X, Y (1 ≤ X, Y ≤ N) which are the nodes for which we need to find the LCA.

Output

Print the node number of the lowest common ancestor.

Example Input

7
1 2
1 3
2 4
2 5
4 7
3 6
4 6

Example Output

1

Problem Solving Process

Now, I will explain the approach to solving the problem. In tree structures, it is common to use DFS (Depth-First Search) or BFS (Breadth-First Search) to store the depth of nodes and record parent nodes. This method allows us to compare the depth of each node and find the common ancestor.

1. Build the Tree

First, we need to build the tree based on the information given in the input. In Kotlin, this can be implemented using a list to store the children of each node.

data class TreeNode(val id: Int) {
    val children = mutableListOf()
}

fun buildTree(n: Int, edges: List>): Map {
    val nodes = mutableMapOf()
    edges.forEach { (parentId, childId) ->
        val parentNode = nodes.getOrPut(parentId) { TreeNode(parentId) }
        val childNode = nodes.getOrPut(childId) { TreeNode(childId) }
        parentNode.children.add(childNode)
    }
    return nodes
}

2. Store Depth and Parent Nodes

We will write a function to store depth and parent nodes using DFS. This will be helpful for finding the LCA later on.

val depth = mutableMapOf()
val parent = mutableMapOf()

fun dfs(node: TreeNode, dep: Int) {
    depth[node.id] = dep
    for (child in node.children) {
        parent[child.id] = node.id
        dfs(child, dep + 1)
    }
}

// Example usage
val root = nodes[1] // Root node (ID: 1)
dfs(root, 0)

3. Find LCA

Now we will implement a function to find the LCA of the two nodes. We will compare the two given nodes to adjust their depths and find the ancestor.

fun findLCA(x: Int, y: Int): Int {
    // Adjust depth
    var a = x
    var b = y
    while (depth[a] > depth[b]) {
        a = parent[a]!!
    }
    while (depth[b] > depth[a]) {
        b = parent[b]!!
    }
    while (a != b) {
        a = parent[a]!!
        b = parent[b]!!
    }
    return a
}

// Example usage
val lca = findLCA(4, 6)
println("LCA: $lca")

4. Full Implementation

Now, we will consolidate all the steps to write the complete program.

fun main() {
    val n = readLine()!!.toInt()
    val edges = mutableListOf>()
    repeat(n - 1) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        edges.add(Pair(a, b))
    }
    val (x, y) = readLine()!!.split(" ").map { it.toInt() }

    val nodes = buildTree(n, edges)

    val depth = mutableMapOf()
    val parent = mutableMapOf()

    fun dfs(node: TreeNode, dep: Int) {
        depth[node.id] = dep
        for (child in node.children) {
            parent[child.id] = node.id
            dfs(child, dep + 1)
        }
    }

    val root = nodes[1]
    dfs(root, 0)

    fun findLCA(x: Int, y: Int): Int {
        var a = x
        var b = y
        while (depth[a] > depth[b]) {
            a = parent[a]!!
        }
        while (depth[b] > depth[a]) {
            b = parent[b]!!
        }
        while (a != b) {
            a = parent[a]!!
            b = parent[b]!!
        }
        return a
    }

    val lca = findLCA(x, y)
    println("LCA: $lca")
}

Optimization

The current method calculates depth and parent nodes using DFS and then finds the LCA. This method operates in O(N) time, and finding the LCA takes O(log N) time complexity. However, for larger values of N, it is possible to utilize optimized algorithms such as “Sparse Table” or “Binary Lifting.” These methods can further reduce time complexity.

Conclusion

In this lecture, we learned about how to find the lowest common ancestor. The LCA problem in tree structures is a common topic in algorithm problems, so it is important to practice thoroughly until it becomes second nature. Try writing and understanding the code step by step. Next time, we will return with another topic. Thank you!

In this lecture, we will explore the “Lowest Common Ancestor” problem and explain step by step how to solve it using Kotlin.

Problem Description

It is a problem of finding the Lowest Common Ancestor (LCA) of two nodes A and B in a given binary tree. The LCA is the deepest node that includes both nodes simultaneously.

For example, let’s assume we have a binary tree like the one below:

        1
       / \
      2   3
     / \
    4   5
    

In this case, the LCA of nodes 4 and 5 is node 2. This is because node 2 is the parent of 4 and 5.

Input Format

The input consists of the root node of the binary tree and two nodes A and B. A and B are one of the nodes in the tree.

Output Format

The output is the LCA node of nodes A and B.

Problem Solving Strategy

1. Recursive Approach: We will explore the tree recursively using the characteristics of the binary tree.
2. Base Condition: If the current node is null or the current node is A or B, return that node.
3. Recursive Call: We will explore the left and right subtrees recursively.
4. Ancestor Determination: If the nodes returned from left and right are both not null, the current node is the LCA.

Code Implementation

Now let’s implement the above algorithm in Kotlin.

data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun lowestCommonAncestor(root: TreeNode?, A: TreeNode?, B: TreeNode?): TreeNode? {
    // Base Condition
    if (root == null || root == A || root == B) {
        return root
    }

    // Explore left and right subtrees
    val left = lowestCommonAncestor(root.left, A, B)
    val right = lowestCommonAncestor(root.right, A, B)

    // If current node is LCA
    return when {
        left != null && right != null -> root // Found in different subtrees
        left != null -> left // Found only in left subtree
        right != null -> right // Found only in right subtree
        else -> null // Not found
    }
}
    

Code Explanation

The code above can be divided into the following key parts:

• data class TreeNode: A data class defining a node in the binary tree.
• lowestCommonAncestor: A recursive function to find the lowest common ancestor.
• After checking the base condition, it explores the left and right subtrees and returns the LCA based on the conditions.

Time Complexity and Space Complexity

The time complexity of this algorithm is O(N). (N is the number of nodes) because it traverses all nodes.

The space complexity is O(H), where H corresponds to the height of the tree. This refers to the space used by the recursive call stack.

Example Input and Output

We can consider the following input:

    Input:
    Tree:
        1
       / \
      2   3
     / \
    4   5
    A = 4
    B = 5

    Output:
    2
    

Conclusion

In this lecture, we have looked in detail at the definition and solution methods for the Lowest Common Ancestor problem using Kotlin. This problem frequently arises in various situations, and by mastering binary tree traversal techniques, you will be equipped to solve many algorithmic problems.