Thread-Safe LRU Cache
Problem
We run a Java microservice that fronts lookups against Cloud Object Storage, and we want a small in-process cache in front of it. Implement an LRU cache with a fixed capacity that supports get(key) and put(key, value) in O(1) average time. When the cache is full, evict the least recently used entry. Both get and put on an existing key count as a "use".
Once the single-threaded version works, I will ask how you would make it safe for concurrent calls from a Tomcat thread pool without wrapping every call in one global lock.
Examples
Example 1 — capacity 2: put(1,"a"), put(2,"b"), get(1) returns "a", put(3,"c") evicts key 2, get(2) returns -1, get(3) returns "c".
Example 2 — capacity 1: put("x",10), put("x",11) overwrites with no eviction, get("x") returns 11, put("y",5) evicts "x", get("x") returns -1.
Constraints
- 1 ≤ capacity ≤ 10^5
- Keys are strings or integers; values are arbitrary objects
getandputmust be O(1) average — be ready to justify it
What they look for
Hash map plus doubly linked list with clean pointer surgery, handling the "update existing key" path, and a sensible concurrency discussion (ConcurrentHashMap + lock striping vs. synchronized vs. just using Caffeine). They want trade-offs, not a full concurrent implementation.