A cache that forgets what you have not used

Build a cache holding at most capacity entries. Two operations arrive in order:

• put key value stores a value. If the cache is full, the least recently used entry is thrown out first.
• get key returns the stored value, or -1 if it is not there.

Both put and get count as using an entry, so either one moves it to the most-recently-used end. Report the answer to each get, in order.

Worked example#

Capacity 2:

The idea#

Two requirements pull in different directions.

Finding a key must be instant. That is a hash map.

Knowing which entry is oldest must also be instant, and using an entry has to move it to the newest end without shifting anything else. A list would do it, but removing from the middle of an array is a walk.

The answer is to use both, pointing at each other:

• a doubly linked list in use order, oldest at the front, newest at the back;
• a hash map from key to the list node holding it.

Then get is: look the key up in the map to get the node, unlink it from wherever it is, and put it on the back. Unlinking is constant time because the node knows its own neighbours, which is exactly what a doubly linked list is for and why a singly linked one will not do.

Eviction is: take the node at the front, and remove its key from the map.

Why the map stores nodes, not values#

If it stored values, you could find the value fast and still have no idea where the entry sits in the order, so you would walk the list to find it. Storing the node is what makes both halves fast at once, and it is the trick worth taking away: two structures, each covering the other's weakness, joined by pointers.

About the input#

capacity, then the operations as a count and that many words, then a count and that many keys, then a count and that many values. A get still has a value in its slot; ignore it.

Constraints#

• 1 <= capacity <= 3000
• 1 <= operations <= 100000