LRU cache

Build a key-value cache with a fixed capacity that evicts the least recently used entry when it is full. get(key) returns the value or a miss, put(key, value) inserts or updates, and both count as a use. Both must run in constant time; the usual answer is a hash map plus a doubly linked list. Some reports ask you to run it over a list of operations and return the lookup results.

Follow-ups reported: make it safe when many threads call it at once, and cut down how often a read has to rewrite the recency order (for example by updating recency lazily or in batches) so reads contend less.