o4-mini-2025-04-16· OpenAI LMArena Human Preference 140K
Can you write me a typescript class that handles LRU cache
- User
Can you write me a typescript class that handles LRU cache
- Assistant
Here’s a fully‐typed, generic LRU Cache implementation in TypeScript. It uses a doubly‐linked list + a Map to achieve O(1)
getandputoperations./** * A node in the doubly linked list */ class DLLNode<K, V> { key: K value: V prev: DLLNode<K, V> | null = null next: DLLNode<K, V> | null = null constructor(key: K, value: V) { this.key = key this.value = value } } /** * LRU Cache Class */ export class LRUCache<K, V> { private capacity: number private map: Map<K, DLLNode<K, V>> = new Map() private head: DLLNode<K, V> | null = null private tail: DLLNode<K, V> | null = null /** * @param capacity maximum number of items in cache */ constructor(capacity: number) { if (capacity <= 0) { throw new Error("Capacity must be greater than 0") } this.capacity = capacity } /** * Get value by key. Marks node as most‐recently used. */ get(key: K): V | undefined { const node = this.map.get(key) if (!node) return undefined // Move the accessed node to head (MRU) this.moveToHead(node) return node.value } /** * Insert or update value by key. * If full, evicts least‐recently used. */ put(key: K, value: V): void { const node = this.map.get(key) if (node) { // Update and move to head node.value = value this.moveToHead(node) } else { // New node const newNode = new DLLNode(key, value) if (this.map.size >= this.capacity) { this.evictLRU() } this.addNode(newNode) this.map.set(key, newNode) } } /** * Remove an item by key */ delete(key: K): boolean { const node = this.map.get(key) if (!node) return false this.removeNode(node) this.map.delete(key) return true } /** * Clear entire cache */ clear(): void { this.head = this.tail = null this.map.clear() } // ----- Internal helpers ----- /** Remove a node from the list */ private removeNode(node: DLLNode<K, V>) { const { prev, next } = node if (prev) prev.next = next else this.head = next if (next) next.prev = prev else this.tail = prev node.prev = node.next = null } /** Add node right after head */ private addNode(node: DLLNode<K, V>) { if (!this.head) { this.head = this.tail = node } else { node.next = this.head this.head.prev = node this.head = node } } /** Move an existing node to head (MRU) */ private moveToHead(node: DLLNode<K, V>) { if (node === this.head) return this.removeNode(node) this.addNode(node) } /** Evict least‐recently used node (tail) */ private evictLRU() { if (!this.tail) return const lruKey = this.tail.key this.removeNode(this.tail) this.map.delete(lruKey) } }Usage Example:
const cache = new LRUCache<string, number>(3) cache.put("a", 1) cache.put("b", 2) cache.put("c", 3) cache.get("a") // 1, order is now a→c→b (a is MRU) cache.put("d", 4) // evicts "b" (LRU) console.log(cache.get("b")) // undefined console.log(cache.get("c")) // 3Time Complexity
- get: O(1)
- put: O(1)
Feel free to tweak or extend (e.g. add stats, async hooks, etc.). 🚀
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.