ArraySort.scala

import scala.annotation.tailrec

object ArraySort extends App {
  val array = Array(23, 4325, 4, 11, 34, 324, 65)

  def bubbleSort(array: Array[Int]): Array[Int] = {
    def swapElements(array: Array[Int]): Int = {
      var swapsCount = 0
      for (i ← 1 until array.length) {
        val leftEl = array(i - 1)
        val rightEl = array(i)

        if (leftEl > rightEl) {
          array(i - 1) = rightEl
          array(i) = leftEl
          swapsCount += 1
        }
      }
      swapsCount
    }

    val outArray = new Array[Int](array.length)
    array.copyToArray(outArray)

    while (swapElements(outArray) > 0) ()
    outArray
  }

  def mergeSort(array: Array[Int]): Array[Int] = {
    def mergeArrays(left: Array[Int], right: Array[Int]): Array[Int] = {
      val result = Array.newBuilder[Int]
      result.sizeHint(left.length + right.length)

      var leftIndex, rightIndex = 0
      while (leftIndex < left.length && rightIndex < right.length) {
        if (left(leftIndex) <= right(rightIndex)) {
          result += left(leftIndex)
          leftIndex += 1
        } else {
          result += right(rightIndex)
          rightIndex += 1
        }
      }

      result ++= left.drop(leftIndex)
      result ++= right.drop(rightIndex)
      result.result()
    }

    array match {
      case Array(_) | Array() ⇒
        array

      case _ ⇒
        val (left, right) = array.splitAt(array.length / 2)
        mergeArrays(mergeSort(left), mergeSort(right))
    }
  }

  def quickSort(array: Array[Int]): Array[Int] = {
    def getPivot(array: Array[Int], _leftIndex: Int, _rightIndex: Int): Int = {
      array(_leftIndex + ((_rightIndex - _leftIndex) / 2))
    }

    def partition(array: Array[Int], _leftIndex: Int, _rightIndex: Int): Int = {
      val pivot = getPivot(array, _leftIndex, _rightIndex)

      var leftIndex = _leftIndex
      var rightIndex = _rightIndex

      while (leftIndex <= rightIndex) {
        while (array(leftIndex) < pivot) leftIndex += 1
        while (array(rightIndex) > pivot) rightIndex -= 1
        if (leftIndex <= rightIndex) {
          val leftEl = array(leftIndex)
          val rightEl = array(rightIndex)
          array(leftIndex) = rightEl
          array(rightIndex) = leftEl
          leftIndex += 1
          rightIndex -= 1
        }
      }
      leftIndex
    }

    def doQuickSort(array: Array[Int], _leftIndex: Int, _rightIndex: Int): Unit = {
      if (_leftIndex < _rightIndex) {
        val partIndex = partition(array, _leftIndex, _rightIndex)
        doQuickSort(array, _leftIndex, partIndex - 1)
        doQuickSort(array, partIndex, _rightIndex)
      }
    }

    val outArray = new Array[Int](array.length)
    array.copyToArray(outArray)
    doQuickSort(outArray, 0, outArray.length - 1)
    outArray
  }

  def binarySearch[T](array: Array[T], target: T)(implicit ord: Ordering[T]): Int = {
    @tailrec
    def binarySearchRec(left: Int, right: Int): Int = {
      if (left > right) return -1

      val middle = math.floor((left + right) / 2).toInt
      val element = array(middle)

      if (ord.lt(element, target)) binarySearchRec(middle + 1, right)
      else if (ord.gt(element, target)) binarySearchRec(left, middle - 1)
      else if (ord.equiv(element, target)) middle
      else -1
    }

    binarySearchRec(0, array.length - 1)
  }

  println(bubbleSort(array).toVector)
  println(mergeSort(array).toVector)
  println(quickSort(array).toVector)
  println(binarySearch(quickSort(array), 324))
}

CalcParser.scala

object CalcParser extends App {
  sealed trait Token
  final case class Number(number: Int) extends Token
  final case object Plus extends Token
  final case object Mul extends Token
  final case class Parens(tokens: Seq[Token]) extends Token

  def parse(str: String): Seq[Token] = {
    def parseNumber(str: Seq[Char], tokens: Seq[Token] = Nil, number: String = ""): Seq[Token] = str match {
      case d :: rest if Character.isDigit(d) ⇒ parseNumber(rest, tokens, number + d)
      case _ ⇒ parseTokens(str, tokens :+ Number(number.toInt))
    }

    def parseParens(str: Seq[Char]): (Parens, Seq[Char]) = {
      def parseParensLength(str: Seq[Char], length: Int = 0, parens: Int = 0): Int = str match {
        case '(' :: rest ⇒ parseParensLength(rest, length + 1, parens + 1)
        case ')' :: _ if parens == 0 ⇒ length
        case ')' :: rest ⇒ parseParensLength(rest, length + 1, parens - 1)
        case c :: rest ⇒ parseParensLength(rest, length + 1)
      }

      val length = parseParensLength(str)
      val tokens = parseTokens(str.take(length))
      (Parens(tokens), str.drop(length + 1))
    }

    def parseTokens(str: Seq[Char], tokens: Seq[Token] = Nil): Seq[Token] = str match {
      case d :: _ if Character.isDigit(d) ⇒ parseNumber(str, tokens)
      case ws :: rest if Character.isWhitespace(ws) ⇒ parseTokens(rest, tokens)
      case '+' :: rest ⇒ parseTokens(rest, tokens :+ Plus)
      case '*' :: rest ⇒ parseTokens(rest, tokens :+ Mul)
      case '(' :: rest ⇒
        val (parens, restStr) = parseParens(rest)
        parseTokens(restStr, tokens :+ parens)
      case _ ⇒ tokens
    }

    parseTokens(str.toList)
  }

  def calculate(tokens: Seq[Token]): Int = tokens match {
    case Number(n) :: Nil ⇒ n
    case Parens(ps1) :: rest ⇒ calculate(Number(calculate(ps1)) +: rest)
    case Number(n1) :: op :: Parens(ps2) :: rest ⇒ calculate(Number(n1) +: op +: Number(calculate(ps2)) +: rest)
    case Number(n1) :: Plus :: Number(n2) :: Mul :: right :: rest ⇒ calculate(Number(n1 + (n2 * calculate(Seq(right)))) +: rest)
    case Number(n1) :: Plus :: Number(n2) :: rest ⇒ calculate(Number(n1 + n2) +: rest)
    case Number(n1) :: Mul :: Number(n2) :: rest ⇒ calculate(Number(n1 * n2) +: rest)
  }

  val tokens = parse("2 + 2 * 2 + (2 + 2 * 2)")
  println(tokens)
  println(calculate(tokens))
  assert(calculate(tokens) == 12)
}

ReverseList.scala

import scala.annotation.tailrec

object ReverseList extends App {
  sealed trait LinkedListNode[T] {
    def next: LinkedListNode[T]
    def reverse: LinkedListNode[T]
    def traverse: Seq[T]
  }

  case class LinkedListNil[T]() extends LinkedListNode[T] {
    def next: LinkedListNode[T] = this
    def reverse: LinkedListNode[T] = this
    def traverse: Seq[T] = Nil
  }

  final case class LinkedList[T](element: T, next: LinkedListNode[T]) extends LinkedListNode[T] {
    def reverse: LinkedList[T] = {
      @tailrec
      def reverseRec(l1: LinkedListNode[T], l2: LinkedListNode[T]): LinkedList[T] = (l1, l2) match {
        case (prev: LinkedList[T], LinkedListNil()) ⇒ prev
        case (prev, list: LinkedList[T]) ⇒ reverseRec(list.copy(next = prev), list.next)
      }

      reverseRec(LinkedListNil(), this)
    }

    def traverse: Seq[T] = {
      element +: next.traverse
    }
  }

  object LinkedList {
    def apply[T](elements: T*): LinkedListNode[T] = {
      if (elements.isEmpty) LinkedListNil[T]()
      else LinkedList(elements.head, apply(elements.tail:_*))
    }
  }

  val list = LinkedList(1, 2, 3, 4, 5)
  println(list)
  println(list.traverse)
  println(list.reverse)
  println(list.reverse.traverse)
}

SQLObfuscator2.scala

import scala.io.Source
import scala.util.matching.Regex

object SQLObfsuscator2 extends App {
  val fieldsToObfuscateByTable = Map("user" → Set("email", "name", "surname"))
  val data = Source.fromURL("https://raw.githubusercontent.com/iwuteam/phptest/master/example.dump.sql").mkString

  val insertRegex = """INSERT INTO `(\w+)`\s*\(([^;]+)\)\s+VALUES\s+([^;]+)[^;]*;""".r

  val result = insertRegex.replaceAllIn(data, { rm ⇒
    val tableName: String = rm.group(1)
    val fieldsToObfuscate: Set[String] = fieldsToObfuscateByTable.getOrElse(tableName, Set.empty)

    val insertFieldsIndices: Map[Int, String] = rm.group(2).split(",\\s*")
      .map(f ⇒ f.drop(1).dropRight(1))
      .zipWithIndex
      .map(v ⇒ (v._2, v._1))
      .toMap

    val insertData: Array[Array[String]] = rm.group(3).split("\\)\\s*,\\s*")
      .map(_.trim.drop(1).split(",\\s*"))

    val newData: Array[Array[String]] = insertData.map(_.zipWithIndex.map { case (data, index) ⇒
      val field = insertFieldsIndices.getOrElse(index, "")
      if (fieldsToObfuscate.contains(field)) "'???'" else data
    })

    val newDataString: String = newData
      .map(_.mkString(","))
      .mkString("(", ",", ")")

    Regex.quoteReplacement(rm.group(0).replace(rm.group(3), newDataString))
  })

  println(result)
}

TestTrie.scala

import scala.collection.SortedMap

//noinspection TypeAnnotation
object TestTrie extends App {
  final case class Trie(suffixes: Int = 0, endsWord: Boolean = false,
                        nodes: SortedMap[Char, Trie] = SortedMap.empty) {

    def addWords(words: String*): Trie = {
      def addWordTo(trie: Trie, word: String): Trie = {
        if (word.isEmpty) {
          trie.copy(endsWord = true)
        } else {
          val subTrie = trie.nodes.getOrElse(word.head, Trie())
          val newTrie = addWordTo(subTrie, word.tail)
          trie.copy(suffixes = trie.suffixes + 1, nodes = trie.nodes + (word.head → newTrie))
        }
      }

      words.foldLeft(this)(addWordTo)
    }

    def traverse(prefix: String): Option[Trie] = {
      if (prefix.isEmpty) Some(this)
      else nodes.get(prefix.head) match {
        case Some(child) ⇒ child.traverse(prefix.tail)
        case None ⇒ None
      }
    }

    def suggest(prefix: String): Seq[String] = {
      def suggestFrom(trie: Trie, currentWord: String): Seq[String] = {
        lazy val subWords = trie.nodes.toStream.flatMap { case (char, subTrie) ⇒
          suggestFrom(subTrie, currentWord + char)
        }

        if (trie.endsWord) Stream(currentWord) #::: subWords
        else subWords
      }

      Stream.empty #::: traverse(prefix).toStream.flatMap(suggestFrom(_, prefix))
    }

    def isWord(word: String): Boolean = {
      if (word.isEmpty) {
        this.endsWord
      } else {
        nodes.get(word.head) match {
          case Some(trie) ⇒ trie.isWord(word.tail)
          case None ⇒ false
        }
      }
    }

    def countSuffixes(prefix: String): Int = {
      if (prefix.isEmpty) {
        this.suffixes
      } else {
        nodes.get(prefix.head) match {
          case Some(child) ⇒ child.countSuffixes(prefix.tail)
          case None ⇒ 0
        }
      }
    }
  }

  val trie = Trie().addWords("apple", "water", "append", "winter", "application")
  // println(trie)
  println(trie.countSuffixes("w"))
  println(trie.isWord("water"))
  println(trie.suggest("app").toVector)
}