Kotlin coding test course, dictionary search

Recently, coding tests have become an essential element in the job market. Many companies use coding tests as a tool to evaluate applicants’ problem-solving skills and algorithmic thinking. In this course, we will explain the process of solving an algorithm problem through the topic of ‘Finding a Word’. This problem will enhance your understanding of string manipulation, sorting, and data structures.

Problem Description

Let’s extend the common problem of finding a word in a dictionary. Given a list of words and a specific word, the task is to determine the position of that word in the dictionary. However, it is assumed that the dictionary is sorted. You need to implement an algorithm that returns the position of the input word in the sorted list of words.

Problem Definition


    fun findWordIndex(dictionary: List, target: String): Int {
        // Initialize the index to return.
        // Return -1 if the word does not exist.
    }

Input

  • dictionary: A sorted list of strings (dictionary)
  • target: The string to find

Output

If the target is found in the dictionary, return the index of the word. Return -1 if it is not found.

Examples


    Input: dictionary = ["apple", "banana", "grape", "kiwi", "melon"], target = "kiwi"
    Output: 3
    
    Input: dictionary = ["apple", "banana", "grape", "kiwi", "melon"], target = "orange"
    Output: -1

Problem Solving Process

This problem is a good candidate for the binary search algorithm. Binary search is an algorithm that quickly finds a specific value in a sorted list, with a time complexity of O(log n). Below, we will explain a step-by-step approach to solving the problem.

Step 1: Understanding the Binary Search Algorithm

The basic idea of binary search is to reduce the search range by half using the ‘midpoint’. The binary search process proceeds as follows:

  1. Set the start index and end index of the list.
  2. Calculate the mid index and check the midpoint value.
  3. Compare the midpoint value with the target value.
  4. If the midpoint value is less than the target, move the start index to mid index + 1.
  5. If the midpoint value is greater than the target, move the end index to mid index – 1.
  6. Recalculate the mid index and repeat steps 2 to 5.
  7. If the target is in the list, return the index; if the end index becomes less than the start index, return -1.

Step 2: Implementing Binary Search in Kotlin

Now let’s implement the above binary search algorithm in Kotlin:


    fun findWordIndex(dictionary: List, target: String): Int {
        var start = 0
        var end = dictionary.size - 1

        while (start <= end) {
            val mid = (start + end) / 2
            when {
                dictionary[mid] == target -> {
                    return mid
                }
                dictionary[mid] < target -> {
                    start = mid + 1
                }
                else -> {
                    end = mid - 1
                }
            }
        }
        return -1 // target does not exist in the list
    }

Step 3: Writing Test Cases

Now we will write some test cases to verify that the implemented algorithm works correctly:


    fun main() {
        val dictionary = listOf("apple", "banana", "grape", "kiwi", "melon")
        println(findWordIndex(dictionary, "kiwi"))  // Answer: 3
        println(findWordIndex(dictionary, "orange")) // Answer: -1
        println(findWordIndex(dictionary, "banana")) // Answer: 1
        println(findWordIndex(dictionary, "apple"))  // Answer: 0
        println(findWordIndex(dictionary, "melon"))  // Answer: 4
    }

Conclusion

In this course, we learned how to solve the algorithm problem of ‘Finding a Word’ using Kotlin. We understood how to efficiently solve the given problem using binary search, which allowed us to build foundational algorithm skills in string searching problems. The process of solving algorithm problems can be improved through repeated practice, so I encourage you to tackle various problems and gain experience.

Thank you!