Scala data structure and complexity O (1)
I had an interview today about Scala and the request was:
Implement a fixed size N data structure with these features:
- get (index)
- set (index, value)
- SETALL (value)
The complexity should be O (1)
example:
val ds = DS(100)
ds.set(4,5)
ds.get(4) //would return 5
ds.set(1,4)
ds.setall(10)
ds.get(4) //would return 10
ds.get(7) //would return 10
ds.set(1,7)
ds.get(1) //would return 7
Please find the code I posted below. My question would be Is this the right solution and if there is a better way to do it?
import scala.collection.mutable.HashMap
trait Operations {
def get(index: Int): Int
def set(index: Int, value: Int)
def setall(value: Int)
}
class DS(N: Int) extends Operations {
var myMutableHashMap = new HashMap[Int, Int]().withDefaultValue(0)
def get(index: Int) = myMutableHashMap(index)
def set(index: Int, value: Int) = {
if (index <= N) myMutableHashMap += (index -> value)
}
def setall(value: Int) = {
myMutableHashMap = new HashMap[Int, Int]().withDefaultValue(value)
}
}
object Task {
def main(args: Array[String]): Unit = {
val ds = new DS(100)
ds.set(4, 5)
ds.get(4)
println(ds.get(4)) // -> 5
ds.setall(10)
println(ds.get(4)) //-> 10
println(ds.get(7)) //-> 10
ds.set(1, 7)
println(ds.get(1)) //-> 7
}
}
+3
source to share
1 answer
I'm not sure if this is better, but I think the HashMap might be a little overkill. The following solution can be smaller and less code. While I would most likely prefer to implement something more general, it should meet the requirements you mentioned.
trait Operations {
def get(index: Int): Int
def set(index: Int, value: Int): Unit
def setall(fill: Int): Unit
}
class DS(size: Int) extends Operations {
val underlying: Array[Int] = new Array(size)
def get(index: Int): Int = underlying(index)
def set(index: Int, value: Int): Unit = underlying(index) = value
def setall(fill: Int): Unit = (0 until size).foreach(underlying(_) = fill)
}
An alternative that just might give us better "hard" difficulty, but at a cost ...
trait Operations {
def get(index: Int): Int
def set(index: Int, value: Int): Unit
def setall(fill: Int): Unit
}
class DS(size: Int) extends Operations {
var underlying: Array[Integer] = new Array(size)
var default: Integer = new Integer(0)
def get(index: Int): Int = {
val result = underlying(index)
if (result == null) default else result
}
def set(index: Int, value: Int): Unit = underlying(index) = value
def setall(fill: Int): Unit = {
default = fill
underlying = new Array(size)
}
}
+1
source to share