Implement LRU cache

[@pratikjain3323]

2 mins into the video, I already know the DS and Algo to be used. Amazing video!

[@ajutamang642]

my CS degree < Tech Dose Content. Keep making sir. I love the content and easy to understand the concepts.

[@techdose4u]

Thanks

[@ArbindYadav-oc3zg]

Damn True 😂😂

[@techdose4u]

😅

[@paragmahajan27]

@@techdose4u Yes. This is very good and great explanation within 10 mins. Pls keep adding such puzzles/algorithms etc, thanks

[@user32132x]

India me teri CSE ke degree mere chaddi se bhi kam value rakhti hai

[@idgaf76]

actually u r pretty gr8 to be a teacher...absolutely amazing

[@techdose4u]

Thanks :)

[@marhawk6468]

Bravo once again, I never got a CS degree so I missed out on a lot. your videos are a blessing!

[@techdose4u]

Thanks

[@SatishKumar-jb9qm]

I like the approach presented to arrive at the final solution - thank you for making this video.

[@techdose4u]

Welcome

[@piyushagarwal3262]

I love your way of teaching. Made all my doubts clear.

[@techdose4u]

Thanks

[@GauravSingh-bo1ys]

This is gold. Thank you very much for this.

[@techdose4u]

Welcome :)

[@saikrishnamohith2000]

Please correct me if i am wrong,
Considering n=cache size and q=query size
Even in hash approach the case where there is a page hit to remove the hitted node and keep it at the rear position it takes O(n) ,so for shifting in this case it takes O(n) and searching O(1) so considering time complexity is calculated referring to worst time complexity ,it takes O(n*q) time complexity even using the hash approach 😅

[@hariprasadcr5936]

Awesomeee...... I've been searching for this everywhere, and the explanation was amazing..... hats off man

[@techdose4u]

Thanks :)

[@hackytech7494]

Thank you so much for such a wonderful explanation

[@techdose4u]

Welcome 😁

[@hangoutwithabhi]

Instead of HashMap we can use Set to store current elements keep updating that on any change with O(1). Searching would also be O(1).

[@adeshpandey6989]

Get is linear operation on set

[@sureshgarine]

awesome explanation. Thank you, sir, felt like remembered OS class in college, of course, this is better than that

[@neharikakhera6411]

Most rearly found explanation

[@kautukraj]

Very helpful, thank you.

[@akshay_g]

Knowledge sharing was good in session. Thanks

[@techdose4u]

Welcome :)

[@ss-xh3hf]

thanks for showing how to optimize step by step

[@techdose4u]

Thanks :)

[@randomcommentor7001]

Brilliant video. Loved the way you explained optimisation stepwise. Thanks. Also, no unnecessary comments. Strictly content.

[@techdose4u]

Thanks

[@Sunny-qq6un]

thanks man , now I am able to solve this question by your helps.

[@mahipalsingh-yo4jt]

very clear and well defined explanation. Thank you..........

[@techdose4u]

Welcome

[@aditya234567]

You didn't mention about updating an existing value, during which we erase existing node even if its in middle of linked list and put it in the front. This erase takes O(n)

[@ShashankKumar-hq2cm]

Yaa it will still take O(N) time complexity in this approach to, because you need to reach that particular position and than remove it.And than further add it at end.

[@suryakiran2970]

insert at beginning i.e. at head -> o(1)

[@sanjeevnirmal1617]

Tum bahut mast kaam karta h bhai

[@AYUSHISHARMABIT]

One of your best videos.
Thank you.

[@techdose4u]

Welcome :)

[@vinayak186f3]

Yt username me roll no. Likhne par exam me zyada aate hai kya ? Har koi likh rha hai 🌚

[@RimjhimSaha369]

Does the Python's in build lru_cache works in the same way as you have written in your code?

[@high-oncode7576]

How its order of 1 time at 8:06
suppose the question given is 1 2 3 "2"
1=2=3 are in cache then if you found 2 then we need to make linked list 1=3=2 is it O(1) now? we need to find where is 2 in the list and put it to the back at front
here ("=" means doubly linked list)

[@ntesla5]

refer his next video in which he explained the code of this

[@manikantabandla3923]

Your point seems acceptable.

[@yasvidobariya1247]

Compare to other channel techdose is underrated...It never happens that i watched your video and feel like wasted time..u are awesome.

[@techdose4u]

Thanks bro :)

[@meghendrasharma787]

Sir can we use circular queue to reduce shifting since the insertion is always done at rear and deletion will be always done from front. also the time taken for both the operation will be 1

[@aneksingh4496]

Nice but I believe u missed the last part in which we have to shift the requested page to the rightmost if gets found in cache

[@techdose4u]

Yes I missed it. Might have mentioned in someone's comment 😅

[@theprotagonist3906]

Liked, subscribed, shared ❤

[@subhamswain2566]

♥️❤️❤️❤️❤️this is awsome sir

[@techdose4u]

Thanks :)

[@shreyasingh542]

You must be working really hard

[@techdose4u]

:)

[@pranushaaa]

Thanks sir. Could understand easily

[@techdose4u]

Nice :)

[@shahedanam2734]

Thanks,it's a very good explanation.

[@techdose4u]

Welcome :)

[@rahulchaubey8988]

Super explaination.👌👌

[@techdose4u]

Thanks :)

[@najimali32]

Approach is good sir.
Writing code in DLL will be lengthy & more difficulty in handling boundary cases.Instead we can use queue ,code will be very compact & easy to handle.
Sir please also make videos on DP question.

[@techdose4u]

Actually this is just for understanding. We will use Deque for this. Internally implementation will be optimized as explained :)

[@najimali32]

@@techdose4u okay sir.

[@md_aaqil8027]

Excellent Explanation sir and keep growing your channel

[@techdose4u]

Thanks :)

[@pradiplamsal1403]

You explain topics pretty well. Thanks for this one

[@techdose4u]

Welcome :)

[@maherukhzafar3093]

Wonderful explanation!!

[@techdose4u]

Thanks

[@satish6155]

I might be wrong but searching a key in a HashMap has worst complexity as O(n) because multiple elements(with same hashcode) can be present in same bucket.

[@babujatoth970]

When we request 4 at 10:26 what if 4 is presented at 2 position?? Pls reply

[@anishsrivastava2885]

In searching suppose an element is present in cache in the middle then we have to move it to front ....it will take O(n) time...how to optimise I it? I am getting TLE for it.

[@sainathreddy2632]

i had implemented the code using singly linked list. the code is given below if there is any mistake please correct it
#include
using namespace std;
struct node
{
int data;
struct node *next;
};
int main()
{
int arr[] = {1, 2, 3, 4, 1, 3};
int n = sizeof(arr) / sizeof(int);
node *front;
node *rear;
node *temp;
node *temp1;
front = (struct node *)malloc(sizeof(struct node));
rear = (struct node *)malloc(sizeof(struct node));
temp = (struct node *)malloc(sizeof(struct node));
temp1 = (struct node *)malloc(sizeof(struct node));
front->data = -1;
rear->data = -1;
int k = 3;
for (int i = 0; i < k; i++)
{
cout data == -1)
{
cout data = arr[i];
front->data = arr[i];
rear = front;
}
else
{
cout next = (struct node *)malloc(sizeof(struct node));
front->next->data = arr[i];
front = front->next;
front->next = NULL;
}
}
cout 0)
{
cout data)
{
cout next;
front->data = op;
}
else
{
int data = temp->data;
temp->next = temp->next->next;
front->next = (struct node *)malloc(sizeof(struct node));
front = front->next;
front->data = data;
}
}
else
{
cout data;
rear = rear->next;
front->next = (struct node *)malloc(sizeof(struct node));
cout

[@souravroychowdhury6525]

amazing explanation !!

[@techdose4u]

Thanks

[@jagadeeshr91]

best one

[@techdose4u]

👍🏼

[@LinnaDu]

very good insights

[@vaibhavchawla2439]

Space complexity is O(size of cache) ? Asking because it is not mentioned in the video.

[@techdose4u]

If you are just using cache then you are correct :)

[@vaibhavchawla2439]

@@techdose4u What are the other things am i missing something?

[@LalitSharma1607]

Brilliant explanation, Thanks

[@techdose4u]

Welcome :)

[@DurgaShiva7574]

very very nice video...but what was the point to store the address of the nodes into the map as a key?... we never made any use of them..is there any use of value (i.e the address of the keys) in the most optimised algorithm ?... please let me know... thanks in advance

[@Rajesh-rg6fw]

The way u explained... It's brilliant.
But i have 2 doubts
1. Hash table size is, random or equal to window size and how to handle collision?
2. What r it's real world implications ?

[@abhishekpratapsingh9283]

Its real world application is related to the memory management of different process that operate in machines.

[@bhawanasahu3000]

Can anyone help me to understand how search operation in Deque takes O(1)? Searching any random index doesn't take O(n) complexity?

[@IT__KumariTejaswini-xv9ii]

Instead of using doubly linked list, can we use queue? because it will also give the time complexity O(1) .. Removing from front nd adding on rear...

[@shresthmishra9329]

Thank you so much TECH DOSE. :3

[@techdose4u]

Welcome :3

[@the_sweet_heaven]

Very good content.

[@techdose4u]

:)

[@yitingg7942]

The deque.remove(element), is this O(1) time ?

[@techdose4u]

Gm 🌄 Don't think so.

[@yitingg7942]

@@techdose4u So we can't use deque then ?

[@techdose4u]

@@yitingg7942 I think in LRU implementation, it could have been done using map if I remeber correctly, along with deque. Then it will be O(1) for remove. I will have to check it.

[@yitingg7942]

@@techdose4u Thanks Surya, I am a little confused that yes by using hashMap we can search for O(1) to see if it's there, to remove in DLL it's O(1) as well. Yes I admit that. However doesn't it take Linear time to search the whole DLL to see position this element is in and then remove it ? I don't use anybody use deque in the discussion, only DLL. So I am very confused.

[@techdose4u]

@@yitingg7942 The time complexity is linear in the number of elements removed. It's implemented like a linked List in C++. It should be similar in Java as well. So yea, O(1) it is.

[@mujahidpasha4440]

Can you explain which is the best algorithm to find the shortest path in a graph... I know there are a bunch of algorithms for that among that which is the optimal and why... Thanks again

[@techdose4u]

Just stick with Dijkstra or else bellman ford for negative edges. It will work.

[@SatyaPrakash-gj5vp]

Really Neat Explanation!
There was an interview question asked what data structure do you use for caching? As per my knowledge i know LinkedHashMap or LinkedHashSet but interviewer asked why not ConcurrentHashMap? Please explain.

[@ap331]

Then your answer would be...that i am not proficient in java...its a java concept

[@thatindianboy2817]

Something related to thread safety?

[@thatindianboy2817]

Btw why can't we use Singly Linked List?

[@venkatasriharsha4227]

What if element is already present at the middle of linked list then removing it will take O(N) again right? Or can we go directly in O(1) since we have address of that element in hashmap?

[@RAHULTHAKUR-ij5xu]

Yup ture hashmap stores address of linked lost nide, being doubly linked link it's easy to associate previous node to next node

[@mujahidpasha4440]

You are awesome....

[@techdose4u]

Thanks :)

[@dhanashreegodase4445]

thank you for making this

[@adityapandey7516]

Sir can't we use Deque here??

[@binod3204]

Hi Sir, why we didn`t use single LL like this... 1-> 2->3 if 4 comes then pointing the head to the 2 and at the tail 4 is added. In this way we don`t need to traverse back to update the variable name. So was there need of doubly. Please help !!

[@HimanshuSharma-sd5gk]

Can we use a circular queue in place of linked list

[@sarthakbhatia7888]

Thanks a lot man !This was an excellent explaination.Just one doubt when we remove an element from an unorderedmap will it be a O(n) operation or O(1) operation??

[@techdose4u]

O(n) worst case. Please read docs.

[@dheerajpoonia2175]

Sir please make video on FARTHEST SEARCH FIRST cache algorithm, it's is difficult to under please

[@techdose4u]

Problem added in todo list. Will make it once I process the earlier requested problems.

[@adarshsharmanit356]

@@techdose4u Queue will be better in LRU cache

[@awesomeps10]

Can't weuse deque instead of a doubly linked list for O(1) deletion and insertion?

[@aayush5474]

yeah i also thought the same

[@avinash-xh6qw]

You can use Either Deque or List or DLL.

[@itvaya]

can anyone tell me which tool is he using for writing the explanations

[@parekshamanchanda8083]

This is how you do it in an interview ❤️❤️

[@techdose4u]

:) Yep

[@radhu8]

Beautiful!

[@techdose4u]

Thanks :)

[@080somyasrivastava6]

How to think which data structure is to be applied ?

[@techdose4u]

Actually you need to figure out the goal of question and the operations you want to perform. Now from your knowledge, you will think what DS to apply to get the job done efficiently. The more you practice, the better you get at deciding good DS & Algo :)

[@NikhilSharma-xv6gx]

Great explanation as always.
A minor doubt, why are we using Doubly Linked list? If its to link yhe previous node, can't we just algorithm for removing node in O(1)?

[@vaibhavchawla2439]

Yes you can but then you won't be able to get the new rear page. The page that will be least recent after removing the current least recent page.
Hence you will need to update to rear to the page 1 before the least recent page that's why doubly linked list.

[@ElifArslan-l9g]

thank you

[@techdose4u]

Welcome :)

[@xlr8tanmay]

Why are we using a Doubly Linked List here?

[@b3arwithm3]

Easy to remove an element

[@SubhamKumar-9009]

nice

[@bestmovies36]

Thank for you

[@haitu8896]

You need to update hashmap, it takes O(n) not O(1)

[@gargsaumya20]

I have a silly doubt. If we use hash function instead of shifting elements in array, then also we have a O(N) space complexity, then how can we say that it can be optimized..?Please bhaiya solve my doubt..

[@bhavya299]

array is fixed size ... won't grow dynamically so linked list is useful

[@somaanilsreeram9555]

Can you do a video on LFU cache as well?

[@techdose4u]

I will try that as well.

[@thatindianboy2817]

Why not single linked list????

[@rahulchaubey8988]

👌👌👌👌

[@divyankgupta4178]

Please explain in simple terms..the main purpose of us students is to solve problem.. not to figure out complex terminologies

[@lovelysen4171]

Where is the code man

[@profesorgaussexpress4959]

you are switching rear with the front!

[@ArpitDhamija]

IB me submit krte hue, 1000 points ke 200 ho gye 😂😂😢😢

[@techdose4u]

🤣 koi baat nhi....sikhne se mtlb hai :)

[@ArpitDhamija]

@@techdose4u testcases of IB are horrible

[@ArpitDhamija]

@@techdose4u sir I have few doubts in IB questions, can you make explanation video of those questions....

[@shaswatdas6553]

#Python code with OrderedDict only
from collections import OrderedDict
class LRU:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def refer(self, k):
print('-----------------Each Iter--------------------')
print('k =', k)
print(self.cache.keys())
if k in self.cache:
self.cache.move_to_end(k, last=False)
return True
else:
self.cache[k] = True
self.cache.move_to_end(k, last=False)
if len(self.cache) > self.capacity:
self.cache.popitem()
return False
# RUNNER
# initializing our cache with the capacity of 2
lru = LRU(4)
print(lru.refer(1))
print(lru.refer(2))
print(lru.refer(3))
print(lru.refer(1))
print(lru.refer(4))
print(lru.refer(5))
print('------------------------Final------------------------')
print(lru.cache.keys())

[@aabhassaxena2490]

1 2 3 4 5 6 3 5 6
You did not covered handling of such cases!

[@techdose4u]

I already covered. When 2nd time 5 comes then you need to reorder the DLL. I already told DLL reordering is required and done in O(1).

[@aabhassaxena2490]

But the deletion of node and changing of pointers u didn't showed,although u explained that

[@techdose4u]

For that we are already using DS and it is too trivial to explain.

[@KarenLee-s6x]

Martin George White Ruth Perez Robert

[@abhishekshrivastava9895]

Your implementation will fail for Test Case :
1 2 3 1 4

[@shaswatdas6553]

#Python code with self implemented doubly linked list
import gc
class Node:
def __init__(self, key):
self.key = key
self.next = self.prev = None
def __str__(self):
return f'{self.key}'
class DoublyLL:
def __init__(self):
self.head = self.last = None
self.size = 0
def insertfirst(self, node):
if self.head is None:
self.head = self.last = node
else:
self.head.prev = node
node.next = self.head
self.head = node
self.size += 1
def deletenode(self, node=None):
if node == None:
node = self.last
self.last = self.last.prev
elif node.next == None:
self.last = self.last.prev
k = node.key
if node.prev is not None:
node.prev.next = node.next
if node.next is not None:
node.next.prev = node.prev
node.next = node.prev = None
gc.collect()
self.size -= 1
# print('deleted', k)
return k
class LRU:
def __init__(self, n):
self.dll = DoublyLL()
self.dict = {}
self.csize = n
def refer(self, k):
print('-----------------Each Iter--------------------')
print('k =', k)
print('Cache:\t', end='')
self.print_cache()
addr = self.dict.get(k)
if addr != None and addr == self.dll.head:
return True
if self.dll.size == self.csize or addr != None:
del_k = self.dll.deletenode(addr)
del self.dict[del_k]
node = Node(k)
self.dll.insertfirst(node)
self.dict[k] = node
return True if addr is not None else False
def print_cache(self):
temp = self.dll.head
while temp is not None:
print(temp, end=' ')
temp = temp.next
print()
lru = LRU(4)
print(lru.refer(1))
print(lru.refer(2))
print(lru.refer(3))
print(lru.refer(1))
print(lru.refer(4))
print(lru.refer(5))
print('------------------------Final------------------------')
lru.print_cache()
print(lru.dll.head)

[@ankitrathore007]

Super explaination 👌👌