When we search a song on Spotify, all your recent searches are stored under recent searches. Let's see how can we build similar functionality.
Understanding the requirements
Let's see all of the functionalities of Spotify's Recent Search Component.
1> Searching a song:
When you search for a song, that song is listed under recent searches, since the list was empty, Coldplay was added first.
2> Searching more songs:
When you search for more songs, the list grows and the songs are pushed on to the list.
Let's fill up the list:
Observations : When we search for something, it's added to the front of the list.
3> Search song when the list is full:
When we search and list is full, the first song ie Coldplay, which was propagated to the end of the list was removed from the list.
Here we get the first glimpse of LRU cache.
LRU = Least Recently Use. Since we initially searched for Coldplay but we didn't search for it again, it was propagated to the back of the list, making it least used component, and hence removed from the list.
This is concept will get clear as we move along.
4> Delete from the list:
Here we removed marshmallow from the list, but the relative ordering was maintained.
5> Searching for a song which was already in the list:
Here Alan Walker was on the list, but we searched for it, hence the Alan Walker card was moved to the front.
What's LRU and why is it useful?
First what's cache?
A cache is basically storage that facilitates high-speed read and writes functionalities.
What's a caching mechanism?
A caching mechanism is a set of operations that would facilitate high-speed read and writes. Since cache size is limited it's important to use an optimal caching mechanism that will take full advantage of a limited cache and store data efficiently.
You might be familiar with this :
What's LRU and why LRU?
LRU is a caching mechanism which performs the following operations:
1> Move the least used item out of the cache when the cache is full.
2> If an item is accessed frequently move it to the front to take advantage of fast read and write speeds.
3> Perform relevant delete and update operations on items.
The main constraint is to perform all operations in O(1) time.
Since I feel that Spotify's example might be a bit confusing, consider this situation.
Your crush is coming over and you want to impress her, so you decide to impress her with your culinary skills by baking pizza for her. So you decide to head to a market and buy ingredients for pizza along with eggs and milk for your breakfast.
We shall consider the cart as our cache, which can hold 5 items.
Let's see the operations we perform, please open the image in new tab and zoom in and go through different LRU operations:
Now you know what's LRU, why use it, what are its applications, let's code it!
Requirements: Design a component / LRU that performs :
1> Add items in O(1).
2> Remove items when overflow in O(1).
3> Delete items in O(1).
4> Get items in O(1).
5> update items in O(1).
Data Structure
HashTable Seems like a good choice, but it's not a list, it doesn't maintain the order in between items.
💡 how about combining two Data structures?
The only issue with HashTables is the ordering, so let's combine a DataStructure with HashTables to serve our purpose.
As you might've guessed stack/queue/tree won't work great with hashtables.
To make our lives a bit easier, instead of going with Singly Linked List, we shall use Doubly Linked List. So that our deletion operation is much faster.
1> Let's Structure our Doubly Linked List:
class DLL {
int key; // stores the key which we will use to reference the item
int val; // stores the actual information
DLL prev; // Points towards previous item
DLL next; // points towards next item
}
2> Let's structure our cache:
Map<Integer,DLL> cache = new HashMap<>();
We shall create key -> Node mappings.
Since it's our custom Doubly Linked List, we shall create 2 Nodes, Head and Tail. These two nodes will help us to add and pop items.
3> Let's structure our operations.
Operations :
movetohead is common among these:
add() : create a node and move it to head
get() : check if the given key exists using hashtable and move it to head
delete is common among these:
delete() : remove the node from its position and discard it
popTail(): remove the node at the tail and discard it
Tricky:
update(): when we update a node,
1> we remove it from its position in the list.
2> move it to head.
Bit of visualization :
(sorry for bad quality, please recommend a good site for creating gifs")
First let's code the functions with the help of which we shall interact with our cache.
// add a new item
public void add(int key,int value){
DLL node = new DLL();
node.key = key;
node.val = value;
this.moveToHead(node);
}
// get a item
public int get(int key){
DLL node = cache.get(key);
if(node == null){
return -1;
}else{
this.moveToHead(node);
return node.val;
}
}
// delete a item
public boolean delete(int key){
DLL node = cache.get(key);
if(node == null) return false;
this.deleteNode(node);
return true;
}
//pop from tail
public void popTail(){
DLL nodeToBeRemove = tail.prev;
DLL newTail = nodeToBeRemove.prev;
newTail.next = tail;
tail.prev = newTail;
}
//update an item
public boolean update(int key,int value){
DLL node = cache.get(key);
if(node == null){
return false;
}else{
node.val = value;
this.deleteNode(node);
this.moveToHead(node);
return true;
}
}
Now let's code the functions which will facilitate working our cache.
public void deleteNode(DLL node){
DLL next = node.next;
DLL prev = node.prev;
next.prev = prev;
prev.next = next;
}
public void moveToHead(DLL node){
DLL next = head.next;
head.next = node;
node.prev = head;
node.next = next;
next.prev = node;
}
Now that we have all the required functions let's put everything together :
class LRUCache {
class DLL{
int val;
int key;
DLL next;
DLL prev;
}
public void moveToHead(DLL node){
DLL next = head.next;
head.next = node;
node.next = next;
next.prev = node;
node.prev = head;
}
public void deleteNode(DLL node){
DLL prev = node.prev;
DLL next = node.next;
prev.next = next;
next.prev = prev;
}
DLL head;
DLL tail;
Map<Integer,DLL> map;
int count;
int capacity;
public LRUCache(int capacity) {
map = new HashMap<>();
this.count = 0;
this.capacity = capacity;
head = new DLL();
tail = new DLL();
head.prev = null;
head.next = tail;
tail.prev = head;
tail.next = null;
}
public int get(int key) {
DLL node = map.get(key);
if(node == null) return -1;
this.moveToHead(node);
return node.val;
}
public void add(int key,int value){
DLL node = cache.get(key);
if(node != null){
this.update(key,value);
}else{
node = new DLL();
node.key = key;
node.val = value;
this.moveToHead(node);
}
public boolean delete(int key){
DLL node = cache.get(key);
if(node == null) return false;
this.deleteNode(node);
cache.remove(key);
return true;
}
public void popTail(){
DLL nodeToBeRemove = tail.prev;
DLL newTail = nodeToBeRemove.prev;
newTail.next = tail;
tail.prev = newTail;
cache.remove(nodeToBeRemove.key);
}
public boolean update(int key,int value){
DLL node = cache.get(key);
if(node == null){
return false;
}else{
node.val = value;
this.deleteNode(node);
this.moveToHead(node);
return true;
}
}
}
That's it! That's the entire LRU implementation. Our version is modular and one can easily remove a functionality if it's not required.
Spotify's recent search component implements only add, delete, poptail. We implemented the rest for completeness.
I hope you like this explanation! And thanks a lot if you made it till here.
If I have made any mistakes or you've any doubts, please do comment.
Top comments (2)
Nice post!
I found a little mistake, the first definition of
moveToHeadis wrong. It's correct when you've put everything together.Should be:
Ohh my that's a blunder mistake! Thanks for pointing that out !!