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

[@marhawk6468]

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

[@techdose4u]

Thanks

[@idgaf76]

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

[@techdose4u]

Thanks :)

[@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 😅

[@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

[@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

[@hariprasadcr5936]

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

[@techdose4u]

Thanks :)

[@GauravSingh-bo1ys]

This is gold. Thank you very much for this.

[@techdose4u]

Welcome :)

[@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 :)

[@sureshgarine]

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

[@hackytech7494]

Thank you so much for such a wonderful explanation

[@techdose4u]

Welcome 😁

[@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 😅

[@akshay_g]

Knowledge sharing was good in session. Thanks

[@techdose4u]

Welcome :)

[@Sunny-qq6un]

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

[@randomcommentor7001]

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

[@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.

[@neharikakhera6411]

Most rearly found explanation

[@techdose4u]

Thanks

[@kautukraj]

Very helpful, thank you.

[@ss-xh3hf]

thanks for showing how to optimize step by step

[@techdose4u]

Thanks :)

[@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)

[@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 🌚

[@sanjeevnirmal1617]

Tum bahut mast kaam karta h bhai

[@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.

[@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.

[@theprotagonist3906]

Liked, subscribed, shared ❤

[@techdose4u]

:)

[@RimjhimSaha369]

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

[@md_aaqil8027]

Excellent Explanation sir and keep growing your channel

[@techdose4u]

Thanks :)

[@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

[@rahulchaubey8988]

Super explaination.👌👌

[@techdose4u]

Thanks :)

[@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.

[@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

[@pradiplamsal1403]

You explain topics pretty well. Thanks for this one

[@techdose4u]

Welcome :)

[@subhamswain2566]

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

[@techdose4u]

Thanks :)

[@shahedanam2734]

Thanks,it's a very good explanation.

[@techdose4u]

Welcome :)

[@pranushaaa]

Thanks sir. Could understand easily

[@techdose4u]

Nice :)

[@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.

[@maherukhzafar3093]

Wonderful explanation!!

[@techdose4u]

Thanks

[@shreyasingh542]

You must be working really hard

[@techdose4u]

:)

[@the_sweet_heaven]

Very good content.

[@techdose4u]

:)

[@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

[@LinnaDu]

very good insights

[@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?

[@souravroychowdhury6525]

amazing explanation !!

[@techdose4u]

Thanks

[@shresthmishra9329]

Thank you so much TECH DOSE. :3

[@techdose4u]

Welcome :3

[@babujatoth970]

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

[@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...

[@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.

[@parekshamanchanda8083]

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

[@techdose4u]

:) Yep

[@LalitSharma1607]

Brilliant explanation, Thanks

[@techdose4u]

Welcome :)

[@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?

[@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

[@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.

[@dhanashreegodase4445]

thank you for making this

[@itvaya]

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

[@adityapandey7516]

Sir can't we use Deque here??

[@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.

[@jagadeeshr91]

best one

[@techdose4u]

👍🏼

[@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?

[@HimanshuSharma-sd5gk]

Can we use a circular queue in place of linked list

[@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 !!

[@theuniquebrokengamer]

If the user wants access the 4th which is at end of the LL we have to move that to the top In doubly and queue we can do that easily

[@mujahidpasha4440]

You are awesome....

[@techdose4u]

Thanks :)

[@radhu8]

Beautiful!

[@techdose4u]

Thanks :)

[@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.

[@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

[@haitu8896]

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

[@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.

[@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 :)

[@SubhamKumar-9009]

nice

[@ElifArslan-l9g]

thank you

[@techdose4u]

Welcome :)

[@xlr8tanmay]

Why are we using a Doubly Linked List here?

[@b3arwithm3]

Easy to remove an element

[@bestmovies36]

Thank for you

[@divyankgupta4178]

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

[@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

[@thatindianboy2817]

Why not single linked list????

[@somaanilsreeram9555]

Can you do a video on LFU cache as well?

[@techdose4u]

I will try that as well.

[@rahulchaubey8988]

👌👌👌👌

[@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.

[@profesorgaussexpress4959]

you are switching rear with the front!

[@lovelysen4171]

Where is the code man

[@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())

[@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....

[@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 👌👌