Design an In-Memory Cache

Let's make an object-oriented design for an in-memory cache, the kind that sits in front of a database and holds a fixed number of recently used values.

Most of this course designs systems out of many classes. This one designs a single component, and the question is different because of it. There is no room to be vague: a cache has to answer in constant time, and the interviewer will ask which structure gives you that. What turns it from a data structure puzzle into a design question is the rule for what leaves when the cache is full, because that rule is the thing most likely to change.