Efficient SortedSet Queries

Efficient SortedSet Queries | CodeSignal Learn

Introduction

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically the SortedSet in Scala, and explore how to handle queries efficiently. This is a common problem, often encountered in numerous data science and algorithmic problems. So, let's gear up to unravel the mysteries of sorted set operations and get our hands dirty with some interactive problem-solving!

O(\log N)

O(\log N)

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

We are tasked with designing a Scala function named processQueries that can process a series of distinct requests or queries efficiently. The queries comprise a list of two integers — the type of operation and the operand. There are three types of operations we'll handle: Adding an integer to the set (operation type 0) Removing an integer from the set (operation type 1). Whenever this operation is invoked, we can guarantee that the integer exists in the set. Finding the smallest integer that is greater than or equal to a given value (operation type 2). The function should return the current size of the set when the operation type is 0 or 1, and the smallest possible integer when the operation type is 2. If such an integer does not exist, the function should return -1. Given a list of queries: Scala List(List(0, 10), List(2, 10), List(0, 20), List(1, 10), List(2, 10)) The function should return: List(1, 10, 2, 1, 20)

To start, we'll initialize our TreeSet in Scala. We'll also create an empty ListBuffer labeled results to store the outputs for each request. Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] // Further logic will go here}

Next, we utilize a for loop to traverse through all the queries. For an operation type of 0 or 1, we either add or remove the provided value from our sorted set. Subsequently, we append the size of the current set to results . Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size // We'll handle operation 2 in the next step case 2 => // Placeholder for now}} results.toList}

Lastly, when the operation type is 2, we need to find the minimum bound, i.e., the smallest value greater than or equal to our provided value in the set. We perform this using the from method and headOption from our TreeSet . If such a value does not exist, we append -1 to results . Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size case 2 => val maybeValue = set.from(value).headOption results += maybeValue.getOrElse(-1)}} results.toList}