LRU Cache Explanation, Application and Design - By Ashay Nayak

Purpose - To give you a complete understanding of LRU cache as a part of interview preparation.

Please like share and comment if you find this helpful.

Skip to the design part below if you know what is LRU cache?

I will try to explain as simply as possible...

We take data from the database but then we thought of retrieving the data faster so we introduced the cache. A cache is a memory that stores data and is used for faster retrieval of data. Generally in the real world, whenever we try to access data, we first go to cache and get the data but if data is not present in cache then we go to the database for getting the data.

Now, a cache has some fixed size. It is obviously in a few GB's. As of now consider that cache is an array of size 3. Initially, this array is empty. Now we want to access data1 and as a cache is empty we get it from a database and now we will put that data1 in a cache as well. So in the future, if we need data1 then we will be able to get it fast from cache only. Similarly, we want to access data2 and data3. We took it from the database and store it in a cache as well. The cache is full now. Now if any request comes for data1 to data 3, we will provide it from the cache.

Now, let's say we need data4 and as it is not present in the cache, we will go to the database and take the data4. As we have no space in cache now, then where will we store the data4? Because we were doing this right? We were taking the data from the database and storing it in cache for fast retrieval in the future. So to do this, we must need to remove some data from an array(our cache) but which one? either data1 or data2 or data3.

To decide this, we will use LRU i.e. least recently used technique. Lemme explain. Consider we have data1 to data 3 in a cache as of now. Now,

1.) we need to access data3 - we take it from a cache

2.) we need to access data1 - we take it from a cache

3.) we need to access data2 - we take it from a cache

So which of the above data have we used recently? - we used data2. Now, which data did we use before that? - we used data1. So which data is least recently used i.e. which data we haven't used for long? - data2. So as per this LRU technique, we will remove data2 and add data4 to the array. Why are we removing the least recently used data? Because we are considering that the least recently used data has fewer chances to come in the future. So data2 has fewer chances that it will be requested in the future again so we removed it from the cache. What if data2 will be requested? Then we get the data2 from the database and update the array. If an array has space then we add it to an array and if not then we will remove the least recently used data from an array and add data2.

Applications of LRU Cache??- see give interviewer applications of cache like:

1.) Cache used in web browsers which store information of previous browsing sessions, recently searched results, etc.

2.) CPU Cache - It stores some basic computer instructions.

3.) Many software have their cache to store software-related data or instructions.

How to design LRU cache??- Interview Question

The best way to implement LRU is?Doubly Linked List and Hash Map.

Time Complexity - O(1) and Space Complexity - O(n).

You can skip to the code below if you have a rough idea of its implementation as comments in code will explain the code.

In LRU, we remove the least recently used data so we need to track recently used data and for that, we are using a doubly-linked list. So when we access the data (either get or put), we add it to the front of the doubly linked list. Let's say we have below doubly linked list and the maximum cache size is 6.

d1 -> d2 -> d3 -> d4 -> d5

Now, let's say we need to?get?d4 then we remove it from the doubly linked list and add it to the front of the doubly linked list. (d4 -> d1 -> d2 -> d3 -> d5). To get the d4, we will traverse DLL and get it i.e. O(n)

Other case, we need to?put?data d6 then we need to add it to the front of the doubly linked list (d6 -> d1 -> d2 -> d3 -> d4 -> d5). This adding operation takes O(1).

Now we need to?put?data d7 then we need to remove d5 from the doubly linked list and add d7 to the front as size is fixed to 6 only (d7 -> d6 -> d1 -> d2 -> d3 -> d4). This adding and removing operations takes O(1) only.

So overall time complexity is O(n).?But we can reduce the time complexity of get operations to O(1) using Hash Map where its values point to the nodes of the DLL.

See Code below, you can also search "lru cache leetcode" on google for practicing the design of lru cache. Leetcode question:

Design a data structure that follows the constraints of a?Least Recently Used (LRU) cache.

Implement the?LRUCache?class:

• LRUCache(int capacity)?Initialize the LRU cache with?positive?size?capacity.
• int get(int key)?Return the value of the?key?if the key exists, otherwise return?-1.
• void put(int key, int value)?Update the value of the?key?if the?key?exists. Otherwise, add the?key-value?pair to the cache. If the number of keys exceeds the?capacity?from this operation,?evict?the least recently used key.

Source Code: https://github.com/AshayNayak/LRU-Cache

Please don't forget to like share and comment if you find this helpful.

Thank you for reading. Share with your friends if you find it helpful.