LRU Cache

A cache with a size limit needs an eviction policy: when it's full and something new arrives, which entry gets thrown out? Least-Recently-Used is the workhorse answer — evict whatever hasn't been touched for the longest. It's behind HTTP caches, database buffer pools, and image caches, and it's a perennial interview question because doing it in O(1) forces you to combine a hash map with an ordering structure.

Implement lruCache(capacity) returning { get, put, size }, where every access marks a key as most-recently-used and inserts past capacity evict the least-recently-used.

Signature

function lruCache(capacity) {
  return { get, put, size };
}

Examples

const c = lruCache(2);
c.put('a', 1);
c.put('b', 2);
c.get('a');    // 1  — 'a' is now most-recently-used
c.put('c', 3); // capacity 2 exceeded -> evict 'b' (the LRU)
c.get('b');    // undefined
c.get('c');    // 3

Notes

• Every use refreshes recency — a get hit and a put that updates an existing key both make that key most-recently-used.
• Evict on overflow — when a new key pushes size past capacity, remove the least-recently-used entry (not the oldest-inserted, if it was used since).
• O(1) target — both operations should be constant time. A Map keeps insertion order, so its first key is the LRU and deleting-then-re-inserting a key moves it to the most-recently-used end.
• Missing keys — get returns undefined; store falsy values (0, '') faithfully.