LeetCode 146. LRU Cache (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@jugzster]

Love that you didn’t edit out your mistakes and expressions. They make the video entertaining, funny, and relatable. Great job explaining, keep it up!

[@SumamaWaheed]

I think It's better to edit the video with a label saying there is a mistake here. At least someone who is new and trying to follow is not confused

[@lowprofile3254]

He does not need to keep it up. WE need to keep it up lol😂

[@nishantkumarbundela8482]

You know I have seen many other videos on youtube regarding these kinds of problems and none of them have shown the number of times they messed up to get an AC. They act like they are coding the problem just at the moment and boom, first-try AC but you really showed the pain one gets after writing 80-100 lines of code and moving the eyes all over it again and again just to catch some goddamn null pointer error and not to mention the frustration it builds up. Respect++;

[@younkezenger8117]

For this question, you either do it right first or debug it for at least half hour. I can't figure out how people can debug the problem like this during an interview.

[@ThyWillBeDone001]

I was asked this at an onsite at Microsoft, I'm surprised watching your video how close I was to the actual implementation. Here I thought I was solving something new lol

[@unknownman1]

did you get the job?

[@reemmohammed4730]

That's an amazing explanation I have ever seen, Thank you, Nick.

[@jianpengyu9843]

Thanks for this video Nick! I followed your video and solved it in python without too much hassle. I think the trick is to use doubly linked list and constantly remove then add to make most frequent ones in front of our linked list.

[@nikhilgupta7532]

I started leaning Java using TheNewBoston tutorials. The best ones I found and it stayed with me for decades. Now I saw your channel and I could feel connected the same way. Thank you for uploading these vids.

[@theceo4744]

I learned Java the exact same way dude. TheNewBoston tutorials are great. I also loves Nick videos as well for the same reasons. Hope we succeed together my friend.

[@mainaakx]

Loved this one. One I originally wrote had too many ifs, adding dummy head and tail sorted it out for me. Thanks!

[@reshihashim4094]

u made it so simple, and let me be honest while u were coding i got i at that point u were linking it the uneven way. thanks for ur effort ❤️

[@jeffreylee911]

Really appreciate your lessons! They are intuitive and easy to understand!

[@hangao8800]

This is awesome! Thank you Nick for making such a helpful video

[@AbhinavKumar-dr4ef]

Seeing your hard work and patience. Salute to you. This problem has so many things to learn. Thank you Nice for your explanation.

[@gnanyreddy3030]

Really awesome video dude. The way you kind of shared the thinking to pick which data structure and why was too good. This would help my thinking about data structures overall. cheers mate..

[@yingjielian4912]

Very Clear! Now I get it! Thanks, keep uploading!

[@sc.smitshah]

I am happy that I am not the only one struggling with this POINTER references crap! Thanks for the video, u are my Java Data Structure saviour!

[@Siddarthathota]

Can you also create a video on HashTable Implementation? Thanks!

[@AsliKalakar]

Is he already posted that ? if not i can help you

[@Luislgsoto]

@@AsliKalakar can you make a vid

[@swagatzeher]

Thank you buddy, the explanation is crisp and clear !

[@shubhamrane9389]

Dude that was just superb, great job.

[@mainulhasan136]

Thank you Nick..I appreciate your work.

[@ChiragMM]

Thank! Nick you are awesome your explaination is always bang on Keep it up. !

[@anurondas3853]

Man every coder has gone through this🤣. The way you reacted was sooo relatable.

[@fancytseng]

omg it is super clear and thank you very very much!!

[@UmairAbid01]

I love you man, thank you for putting up with it, sorry you felt disappointed at the end, happens to best of them out there

[@rutvikpatel3115]

Really appreciated for making this video for us.

[@nanangog]

I got this question in my interview recently

[@adi94071]

do you mind asking which company?

[@nanangog]

@@adi94071 no problem. Its a Singapore Company

[@tolulopemalomo8922]

Thanks for the video, It's really helpful!

[@zhaowencheng8690]

Thx so much for making the video!

[@anirudhatalmale5575]

easiest explanation for implementation of lru cache.

[@LoganKearsley]

You can do better by recycling removed nodes, so once the cache fills you never have to allocate again. Then you can pre-allocate to eliminate branching in the code to add a new value and make it genuinely constant time.

[@ByteMock]

Have seen this in a lot of interviews, we will be covering this soon!

[@sakshigupta1777]

Wonderful explanation 🔥

[@nemanjamilic4818]

What is the difference for implementing LRU for 4-way set associate? Is there any code for that?

[@Bargains20xx]

There is another method of removing a node whose reference is given, copy the data from the next node and delete the next node. That way you dont even need a doubly linked list

[@aritralahiri8321]

Solved it with your help dude

[@hemantkamath1073]

Hi Nick Thank you for this. Can you make a video on LeetCode 460: LFU Cache?

[@DevSoni-yy7th]

Why you pass tail.prev node to delete , if map size will increase to capacity the last node should we delete? Please explain me.

[@jagaya3662]

After watching this video, I spent like 2 days to fully grasp how to create linked lists in Python, one more to finally solve this issue on my own and today rewatched it and implemented your solution in Python xD Great video, I learned a lot in those 3 days.

[@joydeepbhattacharjee3849]

@Jagaya this is the generic solution. In python u actually have a more concise solution. Look into the documentation of OrderedDict

[@anonimettalontana4944]

Why are you worried about the wrong solutions and making mistakes? Debugging is part of the job of a SWE and this makes your videos even more relatable. It is always surprising that KZbinrs explaining leetcode seems to always have the optimal solution given the impression they simply looked it up and are simply explaining it. Thanks for not making a video with the perfect solution without any errors.

[@rafiresearchgroup3994]

I liked a lot the solution presented in the video!!! Here is the Python implementation submitted to Leetcode (Runtime: 220 ms, faster than 55.45% of Python3 online submissions for LRU Cache.) # Use # 1) hash function (for O(1) access to the value) # 2) double linked list (for the cache ordering) class LRUCache: class Node: def __init__(self, key, value): self.value = value self.key = key self.next = None self.prev = None def __init__(self, capacity: int): self.capacity = capacity self.num_of_items = 0 self.hash_map = dict() self.head = None self.tail = None def addNode(self, node): # add node to the head head_current = self.head node.next = head_current self.head = node if head_current == None: # add node to empty list self.tail = node else: # previous head would point to new head. that is 'node' head_current.prev = node def removeNode(self, node): # remove node from somewhere in the list node_next = node.next node_prev = node.prev if (node_next == None): # tail node self.tail = node_prev else: node.next.prev = node_prev if (node_prev == None): # head node (relevant only for Cache with '1' element) self.head = node_next else: node.prev.next = node_next def get(self, key: int) -> int: result = -1 if key in self.hash_map: node = self.hash_map[key] result = node.value # remove the node, and add it to the head of the list self.removeNode(node) #node = self.Node(node.key,node.value) # create new node, with the same value node.next = None node.prev = None self.addNode(node) #print(result) return result def put(self, key: int, value: int) -> None: if key in self.hash_map: # value exists --> refresh # update value and also put at the head of the list node = self.hash_map[key] node.value = value # remove the node, and add it to the head of the list self.removeNode( node) node.next = None node.prev = None self.addNode( node) else: # value not in cache if self.num_of_items >= self.capacity: node = self.tail old_key = node.key if old_key in self.hash_map: del self.hash_map[old_key] else: print('debug-error') self.removeNode(node) # remove self.tail else: # add new value self.num_of_items += 1 node = self.Node(key, value) self.hash_map[key] = node self.addNode(node)

[@mohitswain8441]

LOL! I did it with heaps and hashing, which is of more time complexity and takes more code for implementation.

[@atrichaturvedi6322]

Can it be implemented using Deque because it also implements doubly linked list?

[@prateeksaxena7808]

Yes it can be implemented by deque too.

[@leomonz]

I think it can be done with stack and probably save a lot code but will use lot of memory because get and put all put the element into stack..

[@npchidgopkar]

@Nick, Do you think we could use the timestamp & a tree-based DS for eviction... I was thinking it can save a bit of code & easy to manage... Let me know if I am missing anything if we do it that way

[@sudheerg9182]

tree based DS will not have time complexity of O(1) for any operation so we cant do this using trees. What explained in the video is optimal :-)

[@aniruddhkarekar2818]

I didn't understand the put method in the else condition when we run out of space why do we remove the tail.prev node instead of removing the first node as first node would be least recently used ??

[@jashangill4089]

I got this asked on Google. I was lost. I came with few idea, but could not implement. However, interviewer was good. She told me to search "LRU cache" after the interview. Result: Expecting it to be positive.

[@unknownman1]

Nice

[@Swedishnbkongu]

I'm guessing he catches it later in the video, but he doesn't null check in the remove() method which he should (the tail will have .next be null, so you can't set that next_node's .prev etc...)

[@shiva_krishna_rama]

You can use qeque in c++

[@free-palestine000]

Can you do Integer to English Words on leetcode?

[@harsha.m4026]

+1 from my side

[@TheArmenianSolider65]

Same, its getting asked a lot at amazon right now

[@nehalkashif]

how did you come up with double linked list..

[@mikhailmalinin1774]

You can use standard LinkedList in Java: class LRUCache { int capacity; LinkedList lst; Map map; public LRUCache(int capacity) { this.capacity = capacity; lst = new LinkedList(); map = new HashMap(capacity); } int get(int key) { return map.getOrDefault(key,-1); } void put(int key, int value) { lst.add(key); if(lst.size()>capacity){ Integer toRemove = lst.getFirst(); map.remove(toRemove); lst.removeFirst(); } map.put(key,value); } }

[@TechiiEngineer]

Should’ve we put elements in last when we called det on them

[@dawednesru5353]

thank you

[@Clapzy]

Could we use stack?

[@ivaylopankov7369]

Nice video You could achieve the same with way less code. For example: class LRUCache { LinkedHashMap cache; public LRUCache(int capacity) { this.cache = new LinkedHashMap(capacity, 1.0f, true) { @Override protected boolean removeEldestEntry(Map.Entry e) { return this.size() > capacity; } }; } public int get(int key) { return cache.getOrDefault(key, -1); } public void put(int key, int value) { cache.put(key, value); } }

[@irynasherepot9882]

He could, but often the interviewer on site will not allow using LinkedHashMap, too easy

[@ivaylopankov7369]

Yeah, maybe won't allow using the HashMap as well. Then he will need to implement one hash table, one doubly linked list and to solve the problem for 30 minutes

[@irynasherepot9882]

@@ivaylopankov7369 That can happen too!

[@vibhoo]

Awesome!

[@mdouet]

I solved this problem using a LinkedHashMap for the cache, much simpler than the DoublyLinkedList implementation, but probably less efficient since each time you have to move an element to the tail you have to do a remove() followed by an add(), whereas with a DoublyLinkedList you can accomplish this just by manipulating the next and previous pointers. My solution still finished in 14ms, which is in the top 50% for runtime. Here's the code if anyone is interested: public class LRUCache { private LinkedHashMap cache; private int capacity; public LRUCache(int capacity) { cache = new LinkedHashMap(); this.capacity = capacity; } /** * Remove the key and push it to the tail of the list, and return its value. If * the key does not exist, return -1 instead. * * @param key * @return */ public int get(int key) { int value = -1; if (cache.containsKey(key)) { value = cache.get(key); pushToTail(key, value); } return value; } /** * 1. If we are over capacity, evict the LRU element. 2. If the key we are * adding exists, remove it. 3. Add the new key/value to the tail of the list. * * @param key * @param value */ public void put(int key, int value) { boolean keyExists = cache.containsKey(key); if ((!keyExists) && (cache.size() + 1 > capacity)) { evictLRU(); } if (keyExists) { pushToTail(key, value); } else { cache.put(key, value); } } /** * Remove element at the head of the list (this will be the LRU element). * */ public void evictLRU() { int key = cache.keySet().iterator().next(); cache.remove(key); } public void pushToTail(int key, int value) { cache.remove(key); cache.put(key, value); } }

[@navjotsp]

Can you please explain LFU Cache as well. Thanks

[@hongshanchen154]

you are my god forever

[@moviezach]

You can reduce the number of required data structures by replacing the doubly-linked list and hash map with Java’s LinkedHashMap. Both approaches are technically O(n) memory complexity, where n is the capacity of the cache, but the LinkedHashMap approach should make for simpler code.

[@tiyashasen5020]

Why final keyword is used while instantiating the object at class level. Could you please explain?

[@tommyls4357]

I guess because the dummy HEAD and TAIL nodes never change values;

[@avinavpandey1671]

Can you share the code base?

[@chocolateandmath497]

Why were head and tail not declared in the node class?

[@hamzamusse7853]

I think because the Head and Tail are also nodes. So you define the Node class first. And then you create an instance of the Node class called "Head" and another instance called "Tail". But I'm new to SWE so not 100% sure tbh.

[@Shiva-zy7jq]

Can we use LinkedHashMap instead of HashMap + Doubly LinkedList?

[@dheeraj3281]

Yes, I just did and it worked out perfectly.

[@sudheerg9182]

You can use . linkedhashmap internally uses doubly linkedlist so you should be aware of how put and remove works in linkedhashmap and preferably interviewer may ask us to design everything on our own

[@845aaa]

Why is the hashmap size set as capacity? Isn't that the capacity of cache?

[@TheMrxMF]

It's slightly more optimal, if you preallocate memory (we know that capacity is the largest it will ever get) for the hashmap it doesn't have to rely on dynamically creating more memory which takes up more time.

[@vaibhavjaiswal5911]

How about using a LinkedHashMap?

[@845aaa]

At one point I thought you are gonna throw away stuff and just end the video :p :p

[@prateeknima3388]

Can anybody please explain why do we need to store Key in the Node class as we are storing it in the HashMap?

[@mattgervasio3798]

Remember there is both an integer KEY and integer VALUE. The `val` in the Node class contains the integer VALUE that we want for the provided key. The HashMap key is the KEY we are looking up. Hope that makes sense?

[@tommyls4357]

@@mattgervasio3798 it still doesn't answer do we need to store the KEY in the Node class?

[@aniruddhkarekar2818]

When I write the whole code and then some error occurs my reaction is very similar to yours.. like ohh noo I hate doing this 😂😂

[@om19]

Hi Nick. Thanks a lot for your videos, they're really helpful! But I'm curious if it's fine to provide the following LRU cache implementation if I'll get such question on the interview: class LRUCache extends LinkedHashMap { private final int capacity; public LRUCache(int capacity) { super(capacity + 1, 1.1f, true); this.capacity = capacity; } public int get(int key) { Integer value = super.get(key); return value == null ? -1 : value; } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return super.size() > capacity; } } I have a coding interview with FB in a couple of weeks (mid-October) and it will be my first such experience with the FAANG company. So it would be great to know if this solution will be acceptable since it uses built-in LinkedHashMap functionality. Is it cheating? :)

[@prog112]

Of course this is useless mate, the point of the problem is to solve it by coming up with an algorithm.

[@boiledpotatos4828]

If you are using Java, Deque interface reduces this problem a lot

[@hyzamali5931]

G.O.A.T 🐐

[@laurawu1077]

Thanks! You are sooo cute while you asking how to debug the null pointer

[@yaggeshlikhar6461]

What if we use a list and a hashmap?

[@alisleiman724]

with a simple List ,you dont have access to the tail then it is a problem to remove the least recently used cell.with list you only have the Head.otherwise,with double list,you have access

[@mdouet]

@@alisleiman724 Maybe he meant an ArrayList, in which case you can index any element directly (however I believe these types of operations are O(N)) and things are added to the tail by default.

[@pprkut]

Just FYI, I subscribed.

[@godolsss2139]

why not use a Stack and FIFO

[@NickWhite]

Godol sss this is the most efficient solution

[@paajake]

How will get work? because Stacks or FIFO can only fetch you items with O(1) when your item is at the end or head, but what if your item is at the the other end or in the the middle? then we are getting an O(n) complexity, doesn't satisfy the conditions

[@applefanboytelugu]

7:05

[@dipanshusingh]

❤

[@solomoon4784]

I had never seen this question in my life, I submitted a correct solution in just under 20 min. wait am I a genius ?? just kidding.

[@unknownman1]

oh yes, you definitely are a genius

[@leyocode8868]

Why are we not using Stack instead of a doubly LinkedList , Stack will let you check the latest added key , whenever u hit the capacity u can remove the stack.pop and u let the stack handle that for u ?

[@Meprob]

if we do stack.pop() it will only remove the value at the top of the stack, which would be the most recently added value. If we do stack.pop(0) (remove from the bottom of the stack) that is an O(n) operation.

[@mihirgandhi1222]

Too complex. Can you explain visually what's going on in each method?

[@NickWhite]

Mihir Gandhi if it’s too complex you gotta check out easier problems and build up your understanding before tackling this one

[@NickWhite]

The methods are all pretty standard if you understand linked lists and hashmaps well

[@siobhanahbois]

Try kzbin.info/www/bejne/hHXTqJ1mi7ytZ7c, I like Nick White's videos and I also like Mitch's.

[@Ap-fl2zi]

me when he explains the remove node method: :|

[@NareshKumar-dw9xp]

Hey Nick, where is your welcome clap? LOL

[@rachanashenoy2532]

For removing the node,we know that we are removing it from the tail right? so then why didnt we do this: Node prev=node.prev; prev.next=tail; tail.prev=prev why did you define a new node called next_node which is infact tail node? I hope I am right here

[@reaiswaryaa]

we remove the node from tail only when the capacity is full and need to insert a new node. But there is other case where we need to remove the node when node is accessed (get method) to remove and add it to front of list. When using get method its not necessary the node is at tail.

[@kb3khs]

I'm sad. You are talking about a "figurative cache"... or rather, an abstraction of a cache. I was hoping for info on how CPUs actually implement Pseudo-LRU cache-block replacement policies in L1, L2 cache.