Skip to content

Instantly share code, notes, and snippets.

@manuzhang
Last active December 10, 2018 06:41
Show Gist options
  • Save manuzhang/b8e3810dd6d9f1ed8e890d8d260453ee to your computer and use it in GitHub Desktop.
Save manuzhang/b8e3810dd6d9f1ed8e890d8d260453ee to your computer and use it in GitHub Desktop.
A slow Scala solution for https://leetcode.com/problems/lru-cache/
import scala.collection.mutable
class LRUCache(_capacity: Int) {
var head: Option[Int] = None
var tail: Option[Int] = None
var count = 0
val cache = mutable.Map.empty[Int, Node]
def get(key: Int): Int = {
cache.get(key).map { n =>
moveToEnd(key, n)
n.value
}.getOrElse(-1)
}
def put(key: Int, value: Int): Unit = {
if (cache.contains(key)) {
val n = cache(key).copy(value = value)
cache += key -> n
moveToEnd(key, n)
} else {
if (count >= _capacity) {
head = head.flatMap { k =>
val newHead = cache(k).next.map { nk =>
cache += nk -> cache(nk).copy(prev = None)
nk
}
cache -= k
count -= 1
newHead
}
}
cache += key -> Node(tail, None, value))
count += 1
if (head.isEmpty) {
head = Some(key)
}
tail.foreach { k =>
cache += k -> cache(k).copy(next = Some(key))
}
tail = Some(key)
}
}
private def moveToEnd(key: Int, n: Node): Unit = {
if (count > 1 && n.next.nonEmpty) {
n.prev.foreach { k =>
cache += k -> cache(k).copy(next = n.next)
}
n.next.foreach { k =>
cache += k -> cache(k).copy(prev = n.prev)
}
if (n.prev.isEmpty) {
head = n.next
}
tail.foreach { k =>
cache += k -> cache(k).copy(next = Some(key))
}
cache += key -> n.copy(prev = tail, next = None)
tail = Some(key)
}
}
}
case class Node(prev: Option[Int], next: Option[Int], value: Int)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment