LRU Cache
LRU Cache
30 min·senior·data-structures · maps · doubly-linked-list
Problem
Implement class LRUCache with:
constructor(capacity: number)get(key)→ value or undefined; promotes the entry to most-recentset(key, value)→ adds or updates; evicts the least-recently-used when over capacity
Both ops must be O(1).
Hint: JS Map preserves insertion order. Use that.
Analyze time + space; defend the O(1) claim.
expected time · O(1) get + set
expected space · O(capacity)
12 lines
⏵ run · no run yet · ⌘↵⏵ run · no run yet · tap run