Using a LinkedHashMap here is my favourite solution (quite well known, and used it in a previous interview).

Not sure if this is sometimes considered a shortcut by some interviewers, anyway here's the code.

Matter of taste on inheritance vs composition here.

Complexity is O(1) for both get and put.

import java.util.LinkedHashMap; import java.util.Map; public LRUCache<K, V> extends LinkedHashMap<K, V> { private int cacheSize; public LRUCache(int cacheSize) { super(10, 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() >= cacheSize; } }