Skip to content

Instantly share code, notes, and snippets.

@crates
Last active January 23, 2020 22:02
Show Gist options
  • Save crates/26da669b71519d51b3bf8eb4bdaafbea to your computer and use it in GitHub Desktop.
Save crates/26da669b71519d51b3bf8eb4bdaafbea to your computer and use it in GitHub Desktop.
Least Frequently Used Cache (LFU) in JavaScript - LeetCode Interview Question
// 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