Least Recently Used(LRU) Cache Problem Part1

google image

The problem asks you to build a caching(cache is something that stores computation for lookups or it may also store redundant data for quick access to speed up future requests) system that has all the usual cashing features(i.e insert, delete, search) but it has the ability to get rid of least recently used data. For example: if we have a LRU cache of size 3

v[‘c’] = 2;

v[‘b’] = 4;

v[‘a’] = 1;

Here ‘c’, ‘b’, ‘a’ are the key and 2, 4, 1 are values. Initially, the least recently used pair is v[‘a’] = 1 and the most recently used pair is v[‘c’] = 2 because ‘c’ is the last key we have inserted in the cache. Now if we call get value from the method and pass ‘a’ as the key, then v[‘a’] = 1 becomes the most recently used key-value pair. So, our new cache we’ll be:

v[‘a’] = 1;

v[‘c’] = 2;

v[‘b’] = 4

Then if we want to insert another key-value pair d v[‘d’] = 5 in our LRU cache, we have to get rid of our least recently used key-value pair because the size of our LRU cache is 4. The least recently used pair, in this case, is v[‘b’] = 4. Now our LRU cache becomes

v[‘d’] = 5;

v[‘a’] = 1;

v[c’] = 2;

But if we wanted to insert v[‘a’] = 9 in the LRU cache, we wouldn’t have to remove the least recently used pair, because the key ‘a’ is already in our cache and we just have to overwrite its value and bring the pair at the top as it is the most recently used pair. After inserting v[‘a’] = 9, our LRU cache becomes

v[‘a’] = 9;

v[‘d’] = 5;

v[‘c’] = 2;

So, this is how LRU cache and this is what the problem asks us to implement and we have to do it in constant time(O(1)). You can find this problem at leetcode and interviewbit.

Solution approach

As we are putting key-value pairs in the cache and we have to do the operations in O(1) time, the first data structure that comes to the mind is a hashtable. Hashtable will allow us to insert and access data in constant time, but we cannot delete the least recently used pair using a hashtable in constant time.

google image

But in this case, hashtable won’t work.

We have to think of some other data structure. Hmm...

What about LinkedList? More specifically doubly linked list. If we put the key-value pairs in nodes of a doubly-linked list and we could make the tail of the linked list to store the least recently used cache. In this way we could just remove the last node in constant time, right?

But if we want to access any key-value pair form the doubly linked list, we have to iterate the whole linked list which will take O(n) time. Now what!!

google image

Once again we cannot do all the things in constant time with this data structure too.

We could do a few things in constant time by using hashtable and a few things by using doubly LinkedList. So, why not combine these two? We can make a hashtable that maps the doubly linked list. So, we can do insert, delete and search in constant time.

So, if we do any operations on any of the data, we will make it the head node and if that node was the tails then we have to update tail to point the previous node(tail is our LRU cache).

I will show the implementation LRU Cache on my next post, till then try to solve the problem yourself.