LRU Cache: Debugging Challenge

Debugging challenge - find the bug(s) in this LRU cache.

You are handed a compiling Java LRUCache that does not satisfy its spec, and asked to find what is wrong with it.

Spec:

• get(key) returns the value for the key, or null if absent. Accessing a key makes it the most recently used.
• put(key, value) sets or updates the value. If the cache is at capacity, evict the least recently used entry first. Inserting or updating a key makes it the most recently used.

Worked example given with the problem (capacity 2):

cache = LRUCache(2)
cache.put(1, "a")      # {1: a}
cache.put(2, "b")      # {1: a, 2: b}
cache.get(1)           # "a"  -> 1 is now most recently used
cache.put(3, "c")      # at capacity -> evicts key 2
cache.get(2)           # null (evicted)
cache.get(1)           # "a"  (still present)

The supplied implementation backs the cache with a LinkedHashMap created in insertion order (the given code even carries the comment // insertion order, NOT access order), moves a key to the end on get, and on eviction iterates to the last entry and removes that.

Bonus, asked explicitly: write a failing test case for each bug you find.