Difficulty: Hard, Asked-in: Amazon, Microsoft, Adobe, Google
Key takeaway: an excellent algorithm to learn data structure design and problem-solving using hash tables and doubly-linked lists.
The Least Recently Used (LRU) is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.
So our goal is to design a data structure that follows the constraints of a Least Recently Used (LRU) cache. We need to implement the LRUCache class with the following operations:
We want the following specifications from our LRU cache:
Suppose we have five elements in the main memory, A1 to A5. And let the size of our cache be 3.
Initially, the cache is empty, and all the elements are stored in memory. We want to get A1 first. We get the value of A1 from memory and store it in the cache.
Next, we want to get A2. A2 gets stored at the topmost level, and A1 is moved down as it is no longer the most recently used element.
Next, we want to get A3.
Now suppose we want to get A2 again. Instead of getting this from memory, we can get this from our cache. Notice that the position of A2 is at the top again, as A2 is the most recently used element now.
Now we want to get A4. We have to get it from memory. But where will we store it in our cache? We have to remove some elements so that we can keep A4. So, we remove the least recently used element, A1, in this case.
Since our cache can store only three elements, we need to discard the least recently used element from our cache.
Before designing the implementation of the LRU cache, we will look at the need for a cache. Generally, retrieving data from a computer’s memory is an expensive task. A high-speed memory known as cache memory is used to avoid accessing data from memory repeatedly. A cache holds frequently requested data and instructions to be immediately available to the CPU. Thus, cache memory reduces the average time for accessing data from the main memory.
The cache memory size is generally much smaller than the main memory. So we cannot fit everything from the main memory into the cache. There are different ways of handling this; LRU cache is one such way. The main idea of the LRU cache is to store the n recently accessed elements (assume that the size of the cache is n).
We initialize an array of sizes equal to that of our cache. Here each data element stores extra information to mark with an access time stamp. It shows the time at which the key is stored. We will use the timeStamp to find out the least recently used element in the LRU) cache.
class DataElement
{
int key
int value
int timeStamp
public DataElement(int k, int data, int time)
{
key = k
value = data
timeStamp = time
}
}
int get(int key): we traverse the array and compare the key of each data element with the given key. If we find the key of an element equal to the key, we set the time-stamp of that data element to 0 and return the value of that data element. If we don’t find any such element, we return -1. Time complexity = O(n)
void set(int key, int value): when the array is not full, we increase the time stamp of the existing data in the array by 1, set the time-stamp of the new data to 0, and insert it into the array. When the array space is full, we must delete the least recently used element or data with the largest timestamp. For this, we will iterate through the array and find the element with the largest timeStamp. We will simply insert the new element (with a new key and value) at the place of the element with the largest timeStamp. Time complexity = O(n)
int get(int key): we traverse the linked list and find a data element with a key equal to the key. If it is found, we move the data element to the head of the linked list and return its value. Otherwise, we return -1. Time complexity: O(n)
void set(int key, int value): If the length of the linked list is not equal to the size of our cache, we simply insert the new data element into the head of the linked list. Otherwise, we also need to delete the least recently used element, which is present at the tail of the linked list. Time complexity: O(n)
The critical question is: the time complexity of both get and set operations in both approaches is O(n), which is inefficient and does not satisfy the specification given in the problem. It's an exercise for you to write the implementation code for both approaches!
Solution Idea
When we look at our requirements, we can conclude that we need a set to keep track of the elements present in the cache. But we also need to store them in a specific order, i.e. the least recently used item should be at the bottom, and we should be able to move any item to the top in constant time. So we need to use a doubly-linked list for this. We also need to access an element from the cache in O(1) time. Using the doubly linked list, we will require O(n) time to access any element. Thus, we will need a hash map to map the items to linked list nodes. This allows us to find an element in the linked list in O(1) time.
When inserting new data, insert it into the head of the linked list and record it with a map; after each cache hit, transfer the data (nodes) to be accessed to the head of the linked list; when the linked list is full, discard the tail of the linked list and delete the corresponding map key.
Solution Steps
Following are the steps we need to take whenever we access any element:
If we follow all these steps, we can update our cache in O(1) time as all these steps take O(1) time. Following is the code solution of the question LRU-Cache from Leetcode.
Following are some of the pros and cons of LRU Cache.
Pros:
Cons:
Enjoy learning! Enjoy coding!
You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two-pointers approach provides an efficient solution in O(n) time and O(1) space.
Given a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to the leaf, i.e., the max number of nodes from the root to the most distant leaf. This is an excellent problem to learn problem-solving using DFS and BFS traversal.
Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.
Given an array A[] of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.