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;