Efficient Query Handling Using Kotlin's Sorted Collections

Introduction to Efficient Queries Using Kotlin Sorted Collections

Greetings, budding developers! Today, we're going to dive into the world of data structures, focusing on how to handle queries efficiently using Kotlin . This is a common challenge encountered in various data science and algorithmic scenarios. Let's uncover the intricacies of managing sorted data collections in Kotlin and engage in some interactive problem-solving!

Sorted Collections and Time Complexity

O(\log N)

Task Statement

We are tasked with designing a Kotlin function named processQueries that efficiently processes a series of distinct requests or queries. Each query is a pair of two integers — the type of operation and the operand. The function should handle the following operations: Adding an integer to the collection (operation type 0) Removing an integer (operation type 1). We can ensure that the integer exists in the collection when this operation is invoked. Finding the smallest integer that is greater than or equal to a specified value (operation type 2). The function should return the current size of the collection for operations of type 0 or 1, and the smallest possible integer for operation type 2 . If such an integer does not exist, the function should return -1 . Here’s the list of queries in Kotlin: Kotlin val queries = listOf(Pair(0, 10), Pair(2, 10), Pair(0, 20), Pair(1, 10), Pair(2, 10)) The function should return: [1, 10, 2, 1, 20]

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 3

For operation type 2, we find the smallest integer greater than or equal to the given value. In Kotlin, this can be performed using higher in a SortedSet equivalent. If no appropriate value is found, we add -1 to results.

Kotlin

fun processQueries(queries: List<Pair<Int, Int>>): List<Int> {
    val sortedSet = sortedSetOf<Int>()
    val results = mutableListOf<Int>()

    for (query in queries) {
        val (operation, value) = query

        when (operation) {
            0 -> {
                sortedSet.add(value)
                results.add(sortedSet.size)
            }
            1 -> {
                sortedSet.remove(value)
                results.add(sortedSet.size)
            }
            2 -> {
                val result = sortedSet.ceiling(value)
                results.add(result ?: -1)
            }
        }
    }
    return results
}

fun main() {
    val queries = listOf(
        Pair(0, 10),
        Pair(2, 10),
        Pair(0, 20),
        Pair(1, 10),
        Pair(2, 10)
    )

    val result = processQueries(queries)
    println(result.joinToString(" "))  // Output: 1 10 2 1 20
}

fun processQueries(queries: List<Pair<Int, Int>>): List<Int> {
    val sortedSet = sortedSetOf<Int>()
    val results = mutableListOf<Int>()

    for (query in queries) {
        val (operation, value) = query

        when (operation) {
            0 -> {
                sortedSet.add(value)
                results.add(sortedSet.size)
            }
            1 -> {
                sortedSet.remove(value)
                results.add(sortedSet.size)
            }
            2 -> {
                val result = sortedSet.ceiling(value)
                results.add(result ?: -1)
            }
        }
    }
    return results
}

fun main() {
    val queries = listOf(
        Pair(0, 10),
        Pair(2, 10),
        Pair(0, 20),
        Pair(1, 10),
        Pair(2, 10)
    )

    val result = processQueries(queries)
    println(result.joinToString(" "))  // Output: 1 10 2 1 20
}

Introduction to Efficient Queries Using Kotlin Sorted Collections

Sorted Collections and Time Complexity

Task Statement

Join the 1M+ learners on CodeSignal

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary