Senior LevelJavaScript & TypeScript
How do you implement robust memoization and cache eviction strategies (LRU cache) in JS/TS?
❓ Interview Prompt: Explain LRU (Least Recently Used) cache algorithms, doubly linked lists + Map data structures, and TTL expiration.
An LRU (Least Recently Used) Cache is a finite-capacity data structure that evicts the least recently accessed item when full.
Optimal Implementation Data Structures:
1
JavaScript `Map`: Since ES6, JS Maps maintain key insertion order. Re-inserting an existing key updates its position to the most recently used (end of Map).
2
Doubly Linked List + Hash Map: O(1) time complexity for both
.get(), .set(), and eviction deletions.Code Implementation Example
typescript
class LRUCache<K, V> {
private capacity: number;
private cache: Map<K, V> = new Map();
constructor(capacity: number) {
this.capacity = capacity;
}
get(key: K): V | undefined {
if (!this.cache.has(key)) return undefined;
// Refresh item position to most recently used (end of Map)
const val = this.cache.get(key)!;
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
put(key: K, value: V): void {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
// Evict least recently used (first item in Map) if capacity exceeded
if (this.cache.size > this.capacity) {
const firstKey = this.cache.keys().next().value!;
this.cache.delete(firstKey);
}
}
}💡O(1) LRU Cache implementation utilizing JavaScript Map insertion ordering.
🎯 Interview Key Takeaway
JavaScript Maps retain key insertion order, making them ideal for O(1) LRU cache eviction implementations.
#LRU Cache#Data Structures#Memoization#Senior
Back to all JavaScript & TypeScript Questions→