CareerCup

import org.junit.Test
import org.junit.Assert._

class Problem {
  def findMissingElement(array: Array[Int], target: Int, current: Int = 0): Option[Int] =
    if (current == (array.length - 1)) {
      None
    } else {
      val missingCount = array(current + 1) - array(current) - 1

      if (missingCount >= (target + 1)) {
        Some(array(current) + target + 1)
      } else {
        findMissingElement(array, target - missingCount, current + 1)
      }
    }

  @Test
  def test(): Unit = {
    val numbers = Array(2, 3, 5, 7)

    assertEquals(Some(4), findMissingElement(numbers, 0))
    assertEquals(Some(6), findMissingElement(numbers, 1))
    assertEquals(None, findMissingElement(numbers, 2))
    assertEquals(None, findMissingElement(numbers, 3))
  }
}

case class Visit(from: String, to: String)

object Main {
  def order(visits: Seq[Visit], ordered: Seq[Visit] = Seq()): Seq[Visit] =
    if (visits.isEmpty) {
      ordered
    } else {
      if (ordered.isEmpty) {
        order(visits.tail, Seq(visits.head))
      } else {
        // find preceding visit of first visit of currently oredered visits
        val (preceding, nonPreceding) = visits.partition(_.to == ordered.head.from)

        // find succeeding visit of last visit of currently ordered visits
        val (succeeeding, nonSucceeding) = nonPreceding.partition(ordered.last.to == _.from)

        order(nonSucceeding, preceding ++ ordered ++ succeeeding)
      }
    }

  def main(args: Array[String]): Unit = {
    val unorderedVisits = Seq(
      Visit("ITO", "KOA"),
      Visit("ANC", "SEA"),
      Visit("LGA", "CDG"),
      Visit("KOA", "LGA"),
      Visit("PDX", "ITO"),
      Visit("SEA", "PDX")
    )

    println(order(unorderedVisits))
  }
}

class Node(var value: Int, var parent: Option[Node] = None, var left: Option[Node] = None, var right: Option[Node] = None) {
  override def toString: String = s"Node($value)"
}

object Prob {
  def path(n1: Node, prevPath: Seq[Node] = Seq()): Seq[Node] =
    n1.parent match {
      case Some(parent) =>
        path(parent, prevPath ++ Seq(n1))

      case None =>
        prevPath ++ Seq(n1)
    }

  def commonParent(n1: Node, n2: Node): Node = {
    // find paths up to root node
    val n1Path = path(n1).reverse
    val n2Path = path(n2).reverse

    // pair paths beggining from the root node
    val zipped = n1Path.zip(n2Path)

    // find first non common node in path
    val indexOfFirstNonCommon = zipped.indexWhere(p => !p._1.eq(p._2))

    if (indexOfFirstNonCommon == -1) {
      zipped.last._1
    } else {
      // the node before the first non common node is the common parent 
      zipped(indexOfFirstNonCommon - 1)._1
    }
  }

  def setupParentChild(parent: Node, left: Option[Node], right: Option[Node]): Unit = {
    parent.left = left
    parent.right = right
    left.foreach(_.parent = Some(parent))
    right.foreach(_.parent = Some(parent))
  }

  def main(args: Array[String]): Unit = {
    val n1 = new Node(1)
    val n2 = new Node(2)
    val n3 = new Node(3)
    val n4 = new Node(4)
    val n5 = new Node(5)
    val n8 = new Node(8)
    val n9 = new Node(9)
    val n10 = new Node(10)
    val n11 = new Node(11)

    setupParentChild(n1, Some(n2), Some(n3))
    setupParentChild(n3, Some(n4), Some(n5))
    setupParentChild(n4, Some(n10), None)
    setupParentChild(n5, Some(n8), Some(n9))
    setupParentChild(n9, None, Some(n11))

    println(commonParent(n10, n11))
    println(commonParent(n1, n2))
    println(commonParent(n8, n9))
  }
}

case class LetterOrder(lesser: String, greater: String)

object Prob {
  def main(args: Array[String]): Unit = {
    val orderings = Seq(
      LetterOrder("A", "B"),
      LetterOrder("C", "D"),
      LetterOrder("C", "E"),
      LetterOrder("D", "E"),
      LetterOrder("A", "C"),
      LetterOrder("B", "C")
    )

    val alphabet = orderings
      .flatMap(lo => Seq(lo.lesser, lo.greater))
      .toSet
      .toList

    def sortByOrdering(x: String, y: String): Boolean =
      if (orderings.contains(LetterOrder(x, y))) {
        true
      } else {
        orderings.find(_.lesser == x) match {
          case Some(LetterOrder(_, otherGreater)) =>
            sortByOrdering(otherGreater, y)

          case None =>
            false
        }
      }

    println(alphabet.sortWith(sortByOrdering))
  }
}

For small min and max values brute force recursive just works:

def canFillTheCup(min: Int, max: Int, buttonAmounts: Seq[Int]): Boolean = {
    if (buttonAmounts.exists(ba => min <= ba && ba <= max)) {
      true
    } else {
      buttonAmounts.exists(ba => min - ba > 0 && canFillTheCup(min - ba, max - ba, buttonAmounts))
    }
  }