LeetCode 146. LRU Cache (Algorithm Explained)
Vložit
- čas přidán 5. 10. 2019
- 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 - Věda a technologie
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!
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
He does not need to keep it up. WE need to keep it up lol😂
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++;
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.
That's an amazing explanation I have ever seen, Thank you, Nick.
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
did you get the job?
Loved this one. One I originally wrote had too many ifs, adding dummy head and tail sorted it out for me. Thanks!
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.
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.
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.
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..
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 ❤️
Really appreciate your lessons! They are intuitive and easy to understand!
Seeing your hard work and patience. Salute to you. This problem has so many things to learn. Thank you Nice for your explanation.
This is awesome! Thank you Nick for making such a helpful video
Very Clear! Now I get it! Thanks, keep uploading!
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!
What is the difference for implementing LRU for 4-way set associate? Is there any code for that?
Thank you buddy, the explanation is crisp and clear !
Why you pass tail.prev node to delete , if map size will increase to capacity the last node should we delete? Please explain me.
Can you also create a video on HashTable Implementation?
Thanks!
Is he already posted that ? if not i can help you
@@AsliKalakar can you make a vid
Dude that was just superb, great job.
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 ??
how did you come up with double linked list..
Thank! Nick you are awesome your explaination is always bang on Keep it up. !
Thank you Nick..I appreciate your work.
Really appreciated for making this video for us.
Have seen this in a lot of interviews, we will be covering this soon!
Man every coder has gone through this🤣. The way you reacted was sooo relatable.
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
omg it is super clear and thank you very very much!!
Thanks for the video, It's really helpful!
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.
The mental breakdown at the end was pretty apt! hard relate😂
Thx so much for making the video!
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
easiest explanation for implementation of lru cache.
Hi Nick Thank you for this.
Can you make a video on LeetCode 460: LFU Cache?
Could we use stack?
Can you share the code base?
Can it be implemented using Deque because it also implements doubly linked list?
Yes it can be implemented by deque too.
I got this question in my interview recently
do you mind asking which company?
@@adi94071 no problem. Its a Singapore Company
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..
@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
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 :-)
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...)
Can you please explain LFU Cache as well. Thanks
Wonderful explanation 🔥
Solved it with your help dude
Why final keyword is used while instantiating the object at class level. Could you please explain?
I guess because the dummy HEAD and TAIL nodes never change values;
Can anybody please explain why do we need to store Key in the Node class as we are storing it in the HashMap?
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?
@@mattgervasio3798 it still doesn't answer do we need to store the KEY in the Node class?
You can use qeque in c++
How about using a LinkedHashMap?
Can you do Integer to English Words on leetcode?
+1 from my side
Same, its getting asked a lot at amazon right now
LOL! I did it with heaps and hashing, which is of more time complexity and takes more code for implementation.
Why were head and tail not declared in the node class?
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.
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 CZcamsrs 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.
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.
Nice
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.
@Jagaya this is the generic solution. In python u actually have a more concise solution. Look into the documentation of OrderedDict
Why is the hashmap size set as capacity? Isn't that the capacity of cache?
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.
Awesome!
thank you
Can we use LinkedHashMap instead of HashMap + Doubly LinkedList?
Yes, I just did and it worked out perfectly.
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
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)
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? :)
Of course this is useless mate, the point of the problem is to solve it by coming up with an algorithm.
What if we use a list and a hashmap?
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
@@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.
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.
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);
}
}
He could, but often the interviewer on site will not allow using LinkedHashMap, too easy
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
@@ivaylopankov7369 That can happen too!
you are my god forever
At one point I thought you are gonna throw away stuff and just end the video :p :p
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 😂😂
If you are using Java, Deque interface reduces this problem a lot
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);
}
}
why not use a Stack and FIFO
Godol sss this is the most efficient solution
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
Thanks! You are sooo cute while you asking how to debug the null pointer
Just FYI, I subscribed.
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 ?
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.
7:05
G.O.A.T 🐐
Too complex. Can you explain visually what's going on in each method?
Mihir Gandhi if it’s too complex you gotta check out easier problems and build up your understanding before tackling this one
The methods are all pretty standard if you understand linked lists and hashmaps well
Try czcams.com/video/NDpwj0VWz1U/video.html, I like Nick White's videos and I also like Mitch's.
❤
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);
}
}
Should’ve we put elements in last when we called det on them
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.
oh yes, you definitely are a genius
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
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.
Hey Nick, where is your welcome clap? LOL
me when he explains the remove node method: :|
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.