Scala data structure and complexity O(1)

Question

Today I had an interview about Scala and request was:

Implement a data structure with fixed size N , with these functionalities:

• 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 code that I have sent below.
My question would be Is this right solution and if there is a better way of doing 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

  }

}

Answer 1

I am not sure if it is better, but I think HashMap might be a bit of an overkill. The following solution might have a smaller footprint and takes less code. Although, I would probably rather implement something more generic, it should fulfill 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)
}

Alternative, which just might give us a better 'setall' complexity 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)
  }
}