LeetCode 146. LRU Cache (Algorithm Explained) 

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!

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++;

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

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.

+1 sub for not editing out your mistakes. thank you for boosting our confidence along the learning journey.

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

The mental breakdown at the end was pretty apt! hard relate😂

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.

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

I got this question in my interview recently

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!

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 ❤️

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

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); } }

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

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.

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

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

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)

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 RU-vidrs 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.

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

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

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

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

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

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

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

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

Really appreciated for making this video for us.

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); } }

easiest explanation for implementation of lru cache.

Thank you buddy, the explanation is crisp and clear !

Thanks for the video, It's really helpful!

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

Can you do Integer to English Words on leetcode?

Dude that was just superb, great job.

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

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.

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

Thank you Nick..I appreciate your work.

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.

how did you come up with double linked list..

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

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); } }

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.

Solved it with your help dude

Thx so much for making the video!

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...)

Wonderful explanation 🔥

Can we use LinkedHashMap instead of HashMap + Doubly LinkedList?

@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

You can use qeque in c++

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

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

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

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

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

Could we use stack?

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 😂😂

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

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

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

Can you please explain LFU Cache as well. Thanks

How about using a LinkedHashMap?

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? :)

thank you

Can you share the code base?

you are my god forever

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

why not use a Stack and FIFO

Just FYI, I subscribed.

Awesome!

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

What if we use a list and a hashmap?

G.O.A.T 🐐

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.

7:05

❤

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 ?

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

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

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.

me when he explains the remove node method: :|

Hey Nick, where is your welcome clap? LOL