Messy Medians – HackerRank Solution

In this post, we will solve Messy Medians HackerRank Solution. This problem (Messy Medians) is a part of HackerRank Functional Programming series.

Task

Robin is stuck doing a terminally boring data entry job. She has to enter a lot of numeric observations manually and report running medians after each step to her project lead. The task is sufficiently mind-numbing for her to make a lot of entry errors. Fortunately, she has a keen eye and often notices her mistakes. On the other hand, sometimes she makes mistakes while spotting – or correcting – previous mistakes, and so on.

Your task is to implement a program that will help Robin finish this boring job as soon as possible. The program will accept user input and report a running median for all the observations entered so far. It should also be capable of rolling back to any previous state (including those that were previously rolled back on their own).

Input Format

First line contains an integer,T, the total number of lines to follow.

Each of the following T lines contains either:

1. a positive integer N that will contribute in calculation of the current running median;
2. or a request to roll back to a previous state, which is represented by a negative number between -1 and –M, where M is the total number of queries executed so far. -1 requests a return to the immediately preceding state (which actually results in no state change), while –M requests a return to the state after entering the very first number.

Output Format

Output T integers, representing current running medians after performing operations on corresponding lines in the input.

Constraints

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 10⁹
• 1 ≤ M ≤ number of queries executed so far.

Notes

• You will never be asked to roll back to a non-existent state, or a state for which the running median is not well-defined. In particular, the first line after T will always be a positive number.
• You should print out the median after executing each query, including rollbacks.
• For collections with even number of elements we report the smaller of the two candidate medians.

Sample Input

10
1
5
-2
3
2
5
4
-7
2
-3

Sample Output

1
1
1
1
2
2
3
1
1
3

Explanation

(This represents the collection of the numbers tracked after each step, with median in bold.)

Step 1: 1 -> [1]
Step 2: 5 -> [1, 5]
Step 3: request a return to state after step (3 – 2) = 1 -> [1]
Step 4: 3 -> [1, 3]
Step 5: 2 -> [1, 2, 3]Step 6: 5 -> [1, 2, 3, 5]
Step 7: 4 -> [1, 2, 3, 4, 5]
Step 8: request a return to state after step (8 – 7) = 1 -> [1]
Step 9: 2 -> [1, 2]
Step 10: request a return to state after step (10 – 3) = 7 -> [1, 2, 3, 4, 5]

Solution – Messy Medians – HackerRank Solution

Scala

import java.io.{BufferedReader, IOException, InputStreamReader}
import java.util.StringTokenizer

import scala.collection.immutable.TreeMap

class FastReader() {
  val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
  var st: StringTokenizer = _

  def nextInt: Int = next.toInt

  def nextLong: Long = next.toLong

  def nextDouble: Double = next.toDouble

  def next: String = {
    while (st == null || !st.hasMoreElements)
      try
        st = new StringTokenizer(br.readLine)
      catch {
        case e: IOException =>
          e.printStackTrace()
      }
    st.nextToken
  }

  def nextLine: String = {
    var str = ""
    try
      str = br.readLine
    catch {
      case e: IOException =>
        e.printStackTrace()
    }
    str
  }
}

trait PartialTree {
  def extractMin: (Int, PartialTree)

  def extractMax: (Int, PartialTree)

  def add(v: Int): PartialTree
}

trait Tree extends PartialTree {
  def median: Int

  def add(v: Int): Tree
}

class PartialTreeImpl(val data: TreeMap[Int, Int]) extends PartialTree {
  override def extractMin: (Int, PartialTree) = {
    val (min, count) = data.head
    (min, new PartialTreeImpl(if (count == 1) data.tail else data + (min -> (count - 1))))
  }

  override def extractMax: (Int, PartialTree) = {
    val (max, count) = data.last
    (max, new PartialTreeImpl(if (count == 1) data.init else data + (max -> (count - 1))))
  }

  override def add(v: Int): PartialTree = new PartialTreeImpl(data + (v -> (data.getOrElse(v, 0) + 1)))
}

object PartialTreeImpl {
  def apply(tree: PartialTree, value: Int): PartialTree = tree match {
    case pti: PartialTreeImpl => new PartialTreeImpl(pti.data + (value -> (pti.data.getOrElse(value, 0) + 1)))
    case Empty => new PartialTreeImpl(TreeMap(value -> 1))
  }
}

case object Empty extends Tree {
  override def median: Int = throw new Exception("Median of empty")

  override def add(value: Int): Tree = new Balanced(value, Empty, Empty)

  override def extractMin: (Int, Tree) = throw new Exception("Extract min from empty")

  override def extractMax: (Int, Tree) = throw new Exception("Extract max from empty")
}

class Balanced(val median: Int, left: PartialTree, right: PartialTree) extends Tree {
  override lazy val extractMin: (Int, PartialTree) = left match {
    case Empty => (median, right)
    case _ =>
      val (m, l) = left.extractMin
      (m, new Unbalanced(median, l, right))
  }
  override lazy val extractMax: (Int, PartialTree) = right match {
    case Empty => (median, left)
    case _ =>
      val (m, r) = right.extractMax
      val (mLeft, l) = left.extractMax
      (m, new Unbalanced(mLeft, l, PartialTreeImpl(r, median)))
  }

  override def add(value: Int): Tree = if (value < median) {
    val (m, l) = PartialTreeImpl(left, value).extractMax
    new Unbalanced(m, l, PartialTreeImpl(right, median))
  } else {
    new Unbalanced(median, left, PartialTreeImpl(right, value))
  }
}

class Unbalanced(val median: Int, left: PartialTree, right: PartialTree) extends Tree {
  override lazy val extractMin: (Int, PartialTree) = left match {
    case Empty => (median, right)
    case _ =>
      val (m, l) = PartialTreeImpl(left, median).extractMin
      val (mRight, r) = right.extractMin
      (m, new Balanced(mRight, l, r))
  }
  override lazy val extractMax: (Int, PartialTree) = right match {
    case Empty => (median, left)
    case _ =>
      val (m, r) = right.extractMax
      (m, new Balanced(median, left, r))
  }

  override def add(value: Int): Tree = if (value < median)
    new Balanced(median, PartialTreeImpl(left, value), right)
  else {
    val (m, r) = PartialTreeImpl(right, value).extractMin
    new Balanced(m, PartialTreeImpl(left, median), r)
  }
}

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new FastReader

    val t = sc.nextInt
    val roots = Array.ofDim[Tree](t)
    var root: Tree = Empty

    (0 until t).foreach(i => {
      val v = sc.nextInt
      if (v > 0) {
        root = root.add(v)
      } else {
        root = roots(i + v)
      }

      roots(i) = root
    })

    println(roots.map(_.median).mkString("\n"))
  }
}

Note: This problem (Messy Medians) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.