How do you design an LRU cache, and what does the interviewer expect from your answer?
An LRU cache keeps a fixed number of items and throws out the one that was used least recently when it needs room for a new one. The interviewer wants to see that you can do that quickly, in constant time.
So what does the interviewer expect? Three things.
The first thing is that you can get a value quickly. That means a hash map, because a hash map gives you a key in constant time.
The second thing is that you can mark an item as the most recently used, quickly. A hash map cannot do that, because it has no order. So you need something that keeps its items in order and can move an item to the front cheaply.
The third thing is that you can throw out the oldest item, quickly. That is the item at the other end of the order.
And the answer that satisfies all three is a hash map and a doubly linked list together.
the part what it gives you
-------------------- ----------------------------------------
the hash map a value by key, in constant time
the doubly linked list an order, and a cheap move to the front
the two together everything in constant time
And why a doubly linked list and not a single one? Because you have to be able to remove a node from the middle. When you use an item you move it to the front, and to do that you have to take it out of its current place. A single linked list cannot take a node out without walking from the head, which would be O of n. A doubly linked list has a link to the node before as well as the node after, so the removal is a constant amount of work.
And there are the operations that the cache has to support. The get operation looks up the key, and if it is there then you move it to the front and give back the value. The put operation looks up the key, and if it is there then you update the value and move it to the front. And if it is not there then you put it at the front, and if the cache is now too big then you throw out the one at the back.
And the complexity target is O of 1 for both operations. Every part of every operation has to be constant, and the hash map lookup, the move to the front and the throw out are all constant, so the whole thing is constant.
So the rule to remember is this. A hash map for the lookups and a doubly linked list for the order, and together they give you constant time.
The next two questions in this topic show the easy version and the one written from scratch.