Design an In-Memory Cache

Let's make an object-oriented design for an in-memory cache. This is 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 part, and that changes the question. There is no room to be vague. A cache has to answer in constant time, that is, in the same time no matter how many entries it holds. The interviewer will ask which structure gives you that.

One rule turns this from a data structure puzzle into a design question: what leaves when the cache is full