How to implement an LRU cache

Image courtesy of #craiyon

This is a great interview question due to its layers: simple to get started but challenging to find an optimal solution on the spot. There are a few viable approaches, any of which can be used to demonstrate a candidate’s design and coding skills. In this article, we implement the cache in Java, but the implementation in many languages will be similar.

The code from this article can also be found in this repl.

What is an LRU cache?

Caches are often sized smaller than the entire data set given memory limitations. Not all of the data can be cached, so a design goal is to maximize cache hits (a request that finds the element in the cache). The higher percentage of cache hits, the better the application performance becomes in general. A simple heuristic says to retain items used most recently. If the cache runs out of space, the oldest referenced items are evicted (or removed) in order to make room. This is where the name Least-Recently Used (LRU) comes from.

The formal question

I was asked this question in a Big Tech interview, and I have used it myself numerous times while interviewing senior engineer candidates.

Write a class that implements an LRU cache. The cache only uses String keys and values. It has a defined capacity and evicts the…