Title: Kotlin Coding Test Course, Gift Delivery

This article deals with solving problems that frequently appear in job interviews or algorithm tests, presenting a way to develop both the basics of Kotlin and problem-solving skills through the topic of “Gift Giving.” This problem is based on the fundamental concepts of graph theory and provides logic that can be applied in real life.

Problem Description

The given array gifts contains N people, with the priorities of the gift that need to be delivered to each person listed in order. Each person has a specific number of gifts, and these gifts must be delivered to their counterparts. Our goal is to ensure that everyone receives the exact gifts they want exactly once, while calculating the minimum number of gift delivery actions required to achieve this.

For example, let’s assume the following input is provided:

gifts = [2, 0, 1, 3]

In this case, each person delivers gifts as follows:

  • Person 0: delivers to person 2
  • Person 1: delivers to person 0
  • Person 2: delivers to person 1
  • Person 3: delivers to themselves

Therefore, 3 actions are needed. Let’s implement an algorithm to solve this problem in Kotlin.

Approach to the Problem

To solve this problem, we need to clearly understand each person’s gift delivery and identify the delivery cycle structure. By applying simple exception handling, we can skip any person who does not need to deliver a gift.

Approach

  1. Define the length of the input array gifts as N.
  2. Check the direction of gifts that each person needs to deliver.
  3. Simulate the process of delivering gifts by visiting each person.
  4. Count the size of the group and identify the cycles of received gifts.
  5. Finally, calculate the minimum number of necessary delivery actions.

Code Implementation

Below is the Kotlin code implemented according to the approach above:

fun minGiftTransfers(gifts: IntArray): Int {
    val visited = BooleanArray(gifts.size)
    var transfers = 0

    for (i in gifts.indices) {
        if (!visited[i]) {
            var current = i
            var cycleSize = 0

            do {
                visited[current] = true
                current = gifts[current]
                cycleSize++
            } while (current != i)

            // Exclude the axle (1 gift delivered to each other)
            if (cycleSize > 1) {
                transfers += (cycleSize - 1)
            }
        }
    }

    return transfers
}

// Test case
fun main() {
    val gifts = intArrayOf(2, 0, 1, 3)
    println("The minimum number of actions required for gift delivery is: ${minGiftTransfers(gifts)}")
}

Test Cases

To test the given function, I created several diverse test cases:

  • Test 1: Input gifts = [1, 0]
    expected output = 1 (Person 0 delivers to person 1)
  • Test 2: Input gifts = [1, 2, 0]
    expected output = 1 (3 people are interconnected)
  • Test 3: Input gifts = [1, 2, 3, 4, 0]
    expected output = 4 (Everyone delivers to a different person)
  • Test 4: Input gifts = [0, 1, 2, 3, 4]
    expected output = 0 (Delivers to themselves)

Conclusion

In this tutorial, we explored the process of solving the “Gift Giving” problem using Kotlin. To solve algorithmic problems, it’s essential to clearly understand the requirements and constraints of the problem, and to seek efficient methods to handle them. Through this process, we were able to review the basic syntax of Kotlin while enhancing our ability to structure logic.

Practice other related algorithm problems to gain more experience and improve your competitiveness in algorithm tests!