An implementation of a constant size queue, in which enqueue dequeues the oldest enqueued element. * The performance characteristics of all operations are amortized constant time, due to the fact that * tail, append, and apply (random access) are amortized constant time operations for vectors.

FixedSizeQueue.scala

package com.twitter.mrosenthal.timelines.adhoc.dataset_transform

/**
 * An implementation of a constant size queue, in which enqueue dequeues the oldest enqueued element.
 * The performance characteristics of all operations are amortized constant time, due to the fact that
 * tail, append, and apply (random access) are amortized constant time operations for vectors.
 */
case class FixedSizeQueue[T](elements: Vector[T]){

  def newest: T = elements.last
  def oldest: T = elements.head
  def enqueue(elem: T): FixedSizeQueue[T] = FixedSizeQueue(elements.tail :+ elem)
}

case class Tweet(score: Double)

case class SumScoresAndSubSeq(sumScores:Double, subSeq: Vector[Tweet])

object PositionRelevancePromptsApp extends App {

  /**
   * You are given a sequence of `n` tweets with corresponding scores (between 0 and 1).
   * Find a sub-sequence that maximizes the sum of scores such that there is at least a
   * spacing of `k` between every two consecutive tweets in the sub-sequence.
   * @param scores the original sequence of scores
   * @param spacing the minimal spacing between two consecutive selected elements
   *
   * @throws UnsupportedOperationException in case scores is empty
   */
  def solution(scores: Seq[Tweet], spacing: Int): SumScoresAndSubSeq = {

    val (initializationElements, remainingElements) = scores.splitAt(spacing + 1)

    val initializationVector = initializationElements.foldLeft(Vector.empty[SumScoresAndSubSeq]){
      case (acc, elem) =>
        if(acc.isEmpty || elem.score > acc.last.sumScores ) {
          acc :+ SumScoresAndSubSeq(elem.score, Vector(elem))
        } else {
          acc :+ acc.last
        }
    }

    val queue = FixedSizeQueue(initializationVector)

    val results = remainingElements.foldLeft(queue) {
      case (acc, elem) =>
        if (acc.oldest.sumScores + elem.score > acc.newest.sumScores) {
          acc.enqueue(SumScoresAndSubSeq(acc.oldest.sumScores + elem.score, acc.oldest.subSeq :+ elem))
        } else {
          acc.enqueue(acc.newest)
        }
    }

    results.newest
  }

  // example: prints SumScoresAndSubSeq(0.9,Vector(Tweet(0.4), Tweet(0.5)))
  println(solution(scores = Seq(0.4, 0.3, 0.4, 0.5).map(Tweet.apply), spacing = 1))
}

/**
 * This is a mutable alternative to the immutable FixedSizeQueue
 */
case class MutableFixedSizeQueue[T](elements: Array[T]){

  private var currIndex: Int = elements.length - 1
  def nextIndex: Int = (currIndex + 1) % elements.length

  def newest: T = elements(currIndex)
  def oldest: T = elements(nextIndex)
  def enqueue(elem: T): Unit = {
    elements(nextIndex) = elem
    currIndex = nextIndex
  }
}