LRU Cache
Problem
Design a Least Recently Used cache with a fixed capacity. get(key) returns the value, or −1 if absent, and marks the key as recently used. put(key, value) inserts or updates the key; when the cache is full, it first evicts the least recently used key. Both operations must be O(1).
Example 1
Input: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4) Output: 1, -1, -1, 3, 4
Also asked as: LRU Cache Implementationa · Program for Least Recently Used (LRU) Page Replacement algorithm
Test cases
Case 1
Input: new LRUCache(2) .put(1, 1) .put(2, 2) .get(1) .put(3, 3) .get(2) .put(4, 4) .get(1) .get(3) .get(4) Expected: [null,null,1,null,-1,null,-1,3,4]
Case 2
Input: new LRUCache(1) .put(2, 1) .get(2) .put(3, 2) .get(2) .get(3) Expected: [null,1,null,-1,2]
Case 3
Input: new LRUCache(2) .get(1) .put(1, 10) .put(1, 20) .get(1) .put(2, 2) .put(3, 3) .get(1) .get(2) Expected: [-1,null,null,20,null,null,-1,2]
View solutionHide solution1 approach
1. Hash map + JS Map insertion order
Time O(1) per opSpace O(capacity)
A Map keeps insertion order. On get, delete and re-set the key to mark it most-recent. On put past capacity, delete the first key (least-recent).
class LRUCache { constructor(capacity) { this.cap = capacity; this.map = new Map(); } get(key) { if (!this.map.has(key)) return -1; const v = this.map.get(key); this.map.delete(key); this.map.set(key, v); return v; } put(key, value) { if (this.map.has(key)) this.map.delete(key); else if (this.map.size === this.cap) this.map.delete(this.map.keys().next().value); this.map.set(key, value); }}The "proper" version uses a hash map to nodes of a doubly linked list; same O(1), no reliance on Map ordering.