Last active
January 23, 2020 22:02
-
-
Save crates/26da669b71519d51b3bf8eb4bdaafbea to your computer and use it in GitHub Desktop.
Least Frequently Used Cache (LFU) in JavaScript - LeetCode Interview Question
This file contains hidden or 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
// Designed to solve this LeetCode problem: https://leetcode.com/problems/lfu-cache/ | |
// Author: Crates McD (https://cr8s.net) | |
// Runtime: 420 ms, faster than 8.00% of JavaScript online submissions for LFU Cache. | |
// Memory Usage: 60.2 MB, less than 100.00% of JavaScript online submissions for LFU Cache. | |
/** | |
* @param {any} comparator | |
* @return {boolean} | |
*/ | |
const isNull = comparator => comparator == null; | |
// null comparisons use '==' because strict comparisons don't work against null values! | |
class Node { | |
constructor (key, value) { | |
this.key = key; | |
this.val = value; | |
this.next = this.prev = null; | |
this.freq = 1; | |
} | |
} | |
class DoublyLinkedList { | |
constructor () { | |
this.head = new Node(null, null); | |
this.tail = new Node(null, null); | |
this.head.next = this.tail; | |
this.tail.prev = this.head; | |
} | |
insertHead (node) { | |
node.prev = this.head; | |
node.next = this.head.next; | |
this.head.next.prev = node; | |
this.head.next = node; | |
} | |
removeNode (node) { | |
let prev = node.prev; | |
let next = node.next; | |
prev.next = next; | |
next.prev = prev; | |
} | |
removeTail () { | |
let node = this.tail.prev; | |
this.removeNode(node); | |
return node.key; | |
} | |
isEmpty () { | |
return isNull(this.head.next.val); | |
} | |
} | |
var LFUCache = function (capacity) { | |
this.capacity = capacity; | |
this.currentSize = 0; | |
this.leastFreq = 0; | |
this.nodeHash = new Map(); | |
this.freqHash = new Map(); | |
}; | |
/** | |
* @param {number} key | |
* @return {number} | |
*/ | |
LFUCache.prototype.get = function (key) { | |
let node = this.nodeHash.get(key); | |
if (!node) return -1; | |
this.freqHash.get(node.freq).removeNode(node); | |
if (node.freq === this.leastFreq && | |
this.freqHash.get(node.freq).isEmpty() | |
) this.leastFreq++; | |
node.freq++; | |
if (isNull(this.freqHash.get(node.freq))) { | |
this.freqHash.set(node.freq, new DoublyLinkedList()); | |
} | |
this.freqHash.get(node.freq).insertHead(node); | |
return node.val; | |
}; | |
/** | |
* @param {number} key | |
* @param {number} value | |
* @return {void} | |
*/ | |
LFUCache.prototype.put = function (key, value) { | |
if (this.capacity == 0) return; | |
let node = this.nodeHash.get(key); | |
let newNode; | |
if (!node) { // inserting a new node: | |
this.currentSize++; | |
if (this.currentSize > this.capacity) { | |
let tailKey = this.freqHash.get(this.leastFreq).removeTail(); | |
this.nodeHash.delete(tailKey); | |
this.currentSize--; | |
} | |
newNode = new Node(key, value); | |
if (isNull(this.freqHash.get(1))) { | |
this.freqHash.set(1, new DoublyLinkedList()); | |
} | |
this.freqHash.get(1).insertHead(newNode); | |
this.nodeHash.set(key, newNode); | |
this.leastFreq = 1; | |
} else { // existing node: | |
node.val = value; | |
this.freqHash.get(node.freq).removeNode(node); | |
if (node.freq === this.leastFreq && | |
this.freqHash.get(node.freq).isEmpty() | |
) this.leastFreq++; | |
node.freq++; | |
if (isNull(this.freqHash.get(node.freq))) { | |
this.freqHash.set(node.freq, new DoublyLinkedList()); | |
} | |
this.freqHash.get(node.freq).insertHead(node); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment