Implement a `createLRUCache(capacity)` that supports `get(key)` and `put(key, value)`. When over capacity, evict the least recently used item.
Problem Statement
Examples
Input: const cache = createLRUCache(2); cache.put("a", 1); cache.put("b", 2); cache.put("c", 3); cache.get("a");
Output: null (a was evicted as least recently used)
Explanation: Evicts least recently accessed entry on capacity overflow.
Complexity
Time Complexity: O(N)
Space Complexity: O(1)
Hints
Editorial & Approach
Problem Overview & Intuition
To solve LRU Cache, we consider the execution characteristics of JavaScript engines. Implement a `createLRUCache(capacity)` that supports `get(key)` and `put(key, value)`. When over capacity, evict the least recently used item. By utilizing idiomatic language constructs and clean algorithmic principles, we can accomplish this with optimal time and memory usage.
Step-by-Step Approach
- Understand Problem Contract: Identify input arguments, return type expectations, and edge cases (empty inputs, nullish values).
- Choose Core Mechanism: Use modern JavaScript patterns (use a map which preserves insertion order in javascript).
- Implement Logic: Handle state and transformations efficiently (on get, delete the key and re-insert it to move it to the end (most recent)).
- Return Result: Ensure proper return format and preserve caller context if applicable.
Optimal Implementation (JavaScript)
function createLRUCache(capacity) {
const cache = new Map();
return {
get(key) {
if (!cache.has(key)) return -1;
const val = cache.get(key);
cache.delete(key);
cache.set(key, val);
return val;
},
put(key, value) {
if (cache.has(key)) cache.delete(key);
cache.set(key, value);
if (cache.size > capacity) {
cache.delete(cache.keys().next().value);
}
}
};
}Complexity Analysis
Edge Cases & Corner Traps Handled
- Empty or boundary inputs (empty arrays, strings, zero length).
- Type checks and unexpected values (e.g.
null,undefined, negative numbers). - Closure preservation and memory isolation between separate invocations.