Кotlin Coding Test Course, Finding Building Order

In coding tests, algorithm problems usually involve designing an algorithm to solve a specific problem. In this course, we will tackle the problem titled ‘Finding the Order of Buildings’ using Kotlin.

Problem Description

Given input consists of the height and position of multiple buildings. We need to determine the order in which each building is visible, considering all the given buildings. In other words, we aim to find out how the order is determined when one building is behind another, making it not visible.

Input Format


    The first line contains the number of buildings N (1 ≤ N ≤ 200,000).
    Then, for N lines, each building's height H (1 ≤ H ≤ 10^9) and position P (1 ≤ P ≤ 10^9) are given.

Output Format


    Output N integers representing the order in which each building is visible.

Problem Solving Approach

To solve this problem, we must analyze the relationship between each building’s height and position relative to other buildings. We follow these steps:

  1. Sort the provided buildings based on height and position.
  2. Check each sorted building one by one to determine if it is visible.
  3. Then, count the number of visible buildings to collect the results.

Code Implementation

Now, let’s implement the code in Kotlin to solve the problem based on the discussed approach:


    data class Building(val height: Int, val position: Int)

    fun findVisibleBuildings(buildings: List): List {
        // Sort buildings (sorting by height in descending order)
        val sortedBuildings = buildings.sortedWith(compareByDescending { it.height }.thenBy { it.position })
        val visibleCount = mutableListOf()
        
        var lastHeight = 0
        
        for (building in sortedBuildings) {
            if (building.height > lastHeight) {
                visibleCount.add(building.position)
                lastHeight = building.height
            }
        }
        
        // Sort to return results in original order
        return visibleCount.sorted()
    }

    fun main() {
        val buildingCount = readLine()!!.toInt()
        val buildings = mutableListOf()
        
        for (i in 0 until buildingCount) {
            val (height, position) = readLine()!!.split(" ").map { it.toInt() }
            buildings.add(Building(height, position))
        }
        
        val result = findVisibleBuildings(buildings)
        println(result.joinToString(" "))
    }

Code Explanation

The code above provides comments to explain the flow, but to summarize, it consists of the following steps:

  1. Create a Building data class to hold the building information.
  2. Sort the given buildings in descending order of height.
  3. If the current building’s height is greater than the tallest building checked so far, add its position to visibleCount.
  4. After checking all buildings, return the results sorted in their original order.

Time Complexity Analysis

The time complexity of this algorithm is O(N log N). This is the sum of the time taken to sort the list of buildings and the time taken to find the tallest building. Therefore, it can efficiently handle large datasets.

Conclusion

Through this course, we learned how to solve the ‘Finding the Order of Buildings’ problem using Kotlin. There are various approaches to solving algorithm problems, and understanding and verifying them is crucial. I hope to further enhance coding skills through various problems in the future.

Future References

Thank you!