LRU Cache
Receives a cache capacity and a sequence of put/get operations (semicolon-separated put:key:value / get:key commands) and replays that sequence against a Least Recently Used cache built with that capacity. It maintains the cache as a hash map (key to node) paired with an explicit doubly linked list ordered from most- to least-recently-used: every get moves the accessed key to the front (or returns -1 if the key is absent), and every put either updates and moves an existing key to the front or inserts a new one at the front, evicting the entry at the back (the least recently used) whenever this pushes the cache past capacity — giving O(1) time for both operations. Returns the ordered results of each get command in the sequence, using -1 for a cache miss.
Visualization
- Input
- Result
Algorithm code
// LRU Cache — a single pure function. A Least Recently Used cache is normally
// a stateful class (get/put share instance state); to fit this project's
// single-pure-function contract, both the cache's capacity and its sequence
// of operations are ordinary inputs: `operations` is a semicolon-separated
// string of `put:key:value` / `get:key` commands, replayed against a cache
// built with the given capacity. Internally the cache pairs a Map (key ->
// node) with an explicit doubly linked list in most-recently-used ->
// least-recently-used order, giving O(1) get/put via node splicing.
/**
* @param {number} capacity - maximum number of entries the cache holds
* @param {string} operations - semicolon-separated put:key:value / get:key commands
* @returns {number[]} the result of each `get` command, in order (-1 for a miss)
*/
export function lruCache(capacity, operations) {
const cache = new LRUCache(capacity);
const results = [];
for (const command of operations.split(";")) {
const parts = command.split(":");
if (parts[0] === "put") {
cache.put(Number(parts[1]), Number(parts[2]));
} else {
results.push(cache.get(Number(parts[1])));
}
}
return results;
}
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = Math.max(1, capacity);
this.map = new Map();
this.head = new Node(null, null);
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
const node = this.map.get(key);
if (!node) return -1;
this.moveToFront(node);
return node.value;
}
put(key, value) {
const existing = this.map.get(key);
if (existing) {
existing.value = value;
this.moveToFront(existing);
return;
}
const node = new Node(key, value);
this.map.set(key, node);
this.addToFront(node);
if (this.map.size > this.capacity) {
const lru = this.tail.prev;
this.remove(lru);
this.map.delete(lru.key);
}
}
remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
addToFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
moveToFront(node) {
this.remove(node);
this.addToFront(node);
}
}FUNCTION lruCache(capacity, operations):
cache ← NEW LRUCache(capacity)
results ← empty list
FOR EACH command IN operations SPLIT BY ";":
parts ← command SPLIT BY ":"
IF parts[0] = "put":
cache.put(parts[1], parts[2])
ELSE:
results.APPEND(cache.get(parts[1]))
RETURN results
FUNCTION LRUCache.get(key):
node ← map.get(key)
IF node IS null:
RETURN -1
moveToFront(node)
RETURN node.value
FUNCTION LRUCache.put(key, value):
existing ← map.get(key)
IF existing IS NOT null:
existing.value ← value
moveToFront(existing)
RETURN
node ← NEW Node(key, value)
map.set(key, node)
addToFront(node)
IF map.size > capacity:
lru ← tail.prev
remove(lru)
map.delete(lru.key)