Category: Kotlin coding test

Problem Description

Blu-ray discs are media that can store large amounts of data, including movies, music, and data files.
Recently, a company wants to develop an algorithm to efficiently store data on Blu-ray discs.
Accordingly, each Blu-ray disc has a specific capacity, and multiple files need to be stored on this disc.
Given the sizes of the data to be stored and the maximum capacity of each disc, the problem is to determine the minimum number of discs required.

Input

The first line contains an integer array including the number of data files N (1 ≤ N ≤ 1000) and the size of each file S_i (1 ≤ S_i ≤ 10^6).
The second line gives the maximum capacity of each Blu-ray disc C (1 ≤ C ≤ 10^6).

Output

Output the minimum number of discs.

Example

Input

    5
    2 4 3 6 5
    8
    

Output

    2
    

Approach to the Problem

To solve this problem, the following approach is needed:

1. Sort the sizes of each file and save them to the Blu-ray disc, starting with the largest file.
2. When storing files on the Blu-ray disc, ensure that adding the current file does not exceed the capacity.
3. If there is insufficient capacity to add a file to the current disc, a new disc must be used.
4. Repeat this process until all files are stored to calculate the total number of discs.

Code Implementation

Below is the code written in Kotlin:

fun minNumberOfDisks(fileSizes: List, capacity: Int): Int {
    val sortedFiles = fileSizes.sortedDescending() // Sort file sizes in descending order
    var diskCount = 0
    var currentDiskUsage = 0

    for (fileSize in sortedFiles) {
        if (currentDiskUsage + fileSize > capacity) {
            diskCount++ // Add new disc
            currentDiskUsage = fileSize // Reset disk with current file
        } else {
            currentDiskUsage += fileSize // Add file to current disc
        }
    }

    // Add 1 for the last disc as well
    return diskCount + if (currentDiskUsage > 0) 1 else 0
}

fun main() {
    val fileSizes = listOf(2, 4, 3, 6, 5) // Input file sizes
    val capacity = 8 // Maximum capacity of the Blu-ray disc
    println(minNumberOfDisks(fileSizes, capacity)) // Output result
}
    

Code Explanation

– The minNumberOfDisks function takes a list of file sizes and the disc capacity as input.
– After sorting the file sizes in descending order, it determines the disc to add each file.
– If the current disk usage exceeds the capacity, a new disc is added, and the file usage is reset to the current file.
– After processing all files, the total number of discs is returned.
– The main function verifies the functionality through an example input.

Conclusion

This problem requires an overall understanding of efficient disc management and storage space utilization.
The problem of determining the minimum number of discs required to store all files can be applied in various fields.
Solving algorithmic problems and considering various situations during optimization can enhance programming skills.

Additional Challenges

– When the number of Blu-ray discs is fixed, explore ways to optimize the file placement.
– Implement an algorithm that can handle various capacities of Blu-ray discs.

This course explains the process of solving employment-related algorithm problems using the Kotlin language step by step. This problem is based on the theme ‘Helping the Underprivileged,’ and it will proceed by deriving the correct output for the given input.

        2
        3
        1000 2000 3000
        4
        500 600 700 800
        

        6000
        2000
        2600
        650
        

        fun main() {
            val reader = System.`in`.bufferedReader()
            val T = reader.readLine().toInt() // Number of test cases
            
            repeat(T) {
                val N = reader.readLine().toInt() // Number of donors
                val donations = reader.readLine().split(" ").map { it.toInt() } // List of donations
                
                val total = donations.sum() // Total donations
                val average = total / N.toDouble() // Average donation (including decimals)
                
                println(total) // Print total donations
                println(average.roundToInt()) // Average donation (rounded to the nearest integer)
            }
        }
        

Hello, and welcome to the Kotlin coding test course. In this course, we will delve into the ‘Merge Sort’ algorithm and use it to solve real-world problems. Merge Sort is one of the efficient sorting algorithms with non-zero complexity, which is very useful when sorting large datasets.

1. Introduction to Merge Sort

Merge Sort is an algorithm that employs a Divide and Conquer approach. It splits the array in half, recursively sorts each half, and then merges the two sorted arrays to create a final sorted array. This process can be divided into three major steps:

1. Divide the array in half based on the midpoint
2. Recursively sort each sub-array
3. Merge the two sorted sub-arrays to create the final sorted array

2. Time Complexity of Merge Sort

The time complexity of Merge Sort is O(n log n) in the worst, average, and best cases. This means that the sorting process increases logarithmically based on the number of elements. The space complexity is O(n), requiring additional memory due to the creation of another array to store the sorted results.

3. Understanding the Merge Sort Algorithm

To understand the Merge Sort algorithm, let’s consider the following steps:

3.1. Steps of the Algorithm

1. If the array has one or no elements, it is already sorted, so return it.
2. Split the array into two sub-arrays based on the midpoint index.
3. Recursively call the merge sort function for each sub-array.
4. Merge the two sorted sub-arrays to create one sorted array.

3.2. Implementing Merge Sort

Now, let’s implement the above procedure in Kotlin. Here is a simple code example that implements Merge Sort:

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size < 2) {
        return arr
    }

    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))
    return merge(left, right)
}

fun merge(left: IntArray, right: IntArray): IntArray {
    val merged = IntArray(left.size + right.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            merged[k++] = left[i++]
        } else {
            merged[k++] = right[j++]
        }
    }
    
    while (i < left.size) {
        merged[k++] = left[i++]
    }
    
    while (j < right.size) {
        merged[k++] = right[j++]
    }

    return merged
}

4. Algorithm Problem: Sorting the Given Array

The task is to sort the given array using Merge Sort. The input consists of an array of integers, and the goal is to sort this array and output it. The problem is as follows:

Problem Description

Sort the given array in ascending order using the Merge Sort algorithm.

Input
- The first line contains the size of the array N (1 ≤ N ≤ 1000).
- The second line consists of N integers that form the array.

Output
- Output the N integers sorted in ascending order.

Problem Solving Process

To solve this problem, follow these steps:

1. Call the merge sort function to sort the input array.
2. Output the sorted array.

4.1. Code to Solve the Problem

fun main() {
    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    val sortedArr = mergeSort(arr)

    println(sortedArr.joinToString(" "))
}

5. Example

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

Input:
5
4 2 3 1 5

The output for this input should be:

Output:
1 2 3 4 5

6. Conclusion

Understanding the Merge Sort algorithm is crucial for coding tests. This algorithm is used to solve various problems, so sufficient practice is necessary. In this course, we covered the basic concepts of Merge Sort, its implementation, and how to solve actual coding test problems. We will explore even more diverse algorithms and problem-solving methods in the future, so stay tuned!

1. Introduction

Coding tests are an important step in evaluating essential skills for modern technology jobs. In particular, graph theory is a common topic required in algorithm problems, and among these, the Bellman-Ford algorithm is widely used to solve the problem of finding the shortest path from a single source. In this article, we will implement the Bellman-Ford algorithm using Kotlin and explain the process of solving the problem in detail.

2. Introduction to the Bellman-Ford Algorithm

The Bellman-Ford algorithm is an algorithm for finding the shortest path from one vertex to all other vertices in a given graph. This algorithm is especially useful when there are edges with negative weights. The Bellman-Ford algorithm operates in the following steps:

• Initialize the distance value of the starting vertex to 0 and set the distance values of the other vertices to infinity.
• Repeat for all edges |V| – 1 times, performing distance[v] = min(distance[v], distance[u] + weight(u, v)) for each edge (u, v).
• Finally, check all edges one more time to see if there is a negative weight cycle.

3. Problem Statement

Problem: Finding the Shortest Path

There is a graph as follows. The vertices and edges are given below. The weights of each edge are indicated.

        Vertices:
        0, 1, 2, 3, 4

        Edges:
        0 -> 1 (4)
        0 -> 2 (1)
        1 -> 2 (2)
        1 -> 3 (5)
        2 -> 3 (8)
        3 -> 4 (3)
        2 -> 4 (7)
    

Calculate the shortest path from vertex 0 to all other vertices.

4. Problem Solving Process

4.1 Input Data Design

First, to represent the graph above in code, we need to define vertices and edges as data structures. In Kotlin, this can be easily implemented using lists and data classes.

4.2 Defining Kotlin Data Class

        data class Edge(val u: Int, val v: Int, val weight: Int)
    

4.3 Implementing the Bellman-Ford Algorithm

        fun bellmanFord(edges: List, vertexCount: Int, startVertex: Int): IntArray {
            val distance = IntArray(vertexCount) { Int.MAX_VALUE }
            distance[startVertex] = 0

            for (i in 1 until vertexCount) {
                for (edge in edges) {
                    if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {
                        distance[edge.v] = distance[edge.u] + edge.weight
                    }
                }
            }

            // Validate negative weight cycle
            for (edge in edges) {
                if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {
                    throw IllegalArgumentException("Negative weight cycle exists")
                }
            }

            return distance
        }
    

5. Complete Implementation

        fun main() {
            val edges = listOf(
                Edge(0, 1, 4),
                Edge(0, 2, 1),
                Edge(1, 2, 2),
                Edge(1, 3, 5),
                Edge(2, 3, 8),
                Edge(3, 4, 3),
                Edge(2, 4, 7)
            )
            
            val result = bellmanFord(edges, 5, 0)
            println("Shortest distance from vertex 0 to other vertices: ${result.joinToString(", ")}")
        }
    

6. Output Result

When the above code is executed, you can find out the shortest distances from vertex 0 to all other vertices. The expected result is as follows:

        Shortest distance from vertex 0 to other vertices: 0, 3, 1, 11, 10
    

7. Conclusion

We have looked at the process of solving the shortest path problem using the Bellman-Ford algorithm. This algorithm provides a simple yet powerful functionality. I want to emphasize that it can be particularly useful when there are negative weights. While implementing it using Kotlin, you would have gained a better understanding of how the algorithm works. Practice the Bellman-Ford algorithm as you prepare for coding tests!