LRU Cache (O(1))
Source: Custom (a perennial live-coding question)
Topics: doubly-linked list, hash map, generics, O(1) eviction
Problem
Implement a fixed-capacity Least-Recently-Used cache with O(1) Get and Put. This is
one of the most common systems live-coding questions — and the eviction policy behind most caching
layers a gateway runs.
Requirements:
New[K comparable, V any](capacity int) *LRU[K, V]Get(key) (V, bool) — return the value and mark it most-recently-used; (zero, false) if absent.Put(key, value) — insert/update and mark most-recently-used; if over capacity, evict the
least-recently-used entry.Len() int — current number of entries.- Both operations must be O(1) (no scanning) and safe for concurrent use.
type LRU[K comparable, V any] struct { ... }
func New[K comparable, V any](capacity int) *LRU[K, V]
func (c *LRU[K, V]) Get(key K) (V, bool)
func (c *LRU[K, V]) Put(key K, value V)
func (c *LRU[K, V]) Len() int
Key concepts
- Map + doubly-linked list: the map gives O(1) lookup to a list node; the list gives O(1)
move-to-front and O(1) eviction from the back. Neither structure alone is O(1) for both.
- Sentinel head/tail nodes: dummy nodes at both ends remove all the nil-checking around
insert/remove — every real node always has a non-nil
prev and next.
- Recency = position: front of the list is most-recently-used, back is least.
Get and Put
both move the touched node to the front; eviction always removes the node before the tail
sentinel.
- Why not a slice/ring: a slice forces O(n) shifts on every access; the linked list is what
keeps eviction and promotion O(1).
Run
go test -v -race ./challenges/concurrency/lru-cache/
Sign in to submit your solution.