Last active
May 15, 2019 07:57
-
-
Save MishaelRosenthal/e6d40094876febb6e63475139d462d3e to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment