Hey, awesome video! This is super clear. In the case of needing to remove a key from the count dict that has multiple keys at the lowest count: I think we would want a doubly linked list so that we can remove the least recently used item at the head of the list. If we use a stack, popping the stack will get the most recent one put in that count index because it will be the last one in (LIFO).
Hey Tryler, short answer: you're right. Longer answer: that's fundamentally how this solution is actually implemented, although it leverages some built in functionality within Python. In particular, you'll notice on line 10 that we're initializing an `OrderedDict`. This is the equivalent of a dictionary, but is actually backed by a linked list. When I'm calling the `popitem` function on line 35, I'm choosing to pop from the beginning and not the end (hence the `last=False` bit). With the OrderedDict, we can move any element within it to the front or back of the linked list, which allows us to pop items off in constant time. If you're either not familiar with Python, or not familiar with the underlying implementation of the `OrderedDict`, I agree that this definitely doesn't seem obvious. Did this address what you were mentioning? Or did I misinterpret the question? LMK!
Intuitively I solved this by using one dict and one DLL, where the DLL was ordered by frequency first and recency second, this way every time max capacity was reached I only had to remove the tail element. It got accepted but is only faster than 7%, is that fine or should I look at other approaches????
On the surface it seems sound to me. Remember that the most important piece about your interviews will be the conversations you have in getting to the answer! Being open to discussing pros & cons of your proposal(s) and keeping an open dialogue on how to continuously improve the code is what will get you over the line, *not* necessarily having the 99.99th percentile fastest code.
Just so you know, your implementation leaves empty defaultdicts behind. It still works, but causes the memory usage to grow over time, despite the cache capacity.
![[Java] Leetcode 460. LFU Cache [Design #4]](/img/n.gif)
Thank you so much for giving a great explanation.
my pleasure!
Hey, awesome video! This is super clear.
In the case of needing to remove a key from the count dict that has multiple keys at the lowest count:
I think we would want a doubly linked list so that we can remove the least recently used item at the head of the list.
If we use a stack, popping the stack will get the most recent one put in that count index because it will be the last one in (LIFO).
Hey Tryler, short answer: you're right. Longer answer: that's fundamentally how this solution is actually implemented, although it leverages some built in functionality within Python. In particular, you'll notice on line 10 that we're initializing an `OrderedDict`. This is the equivalent of a dictionary, but is actually backed by a linked list. When I'm calling the `popitem` function on line 35, I'm choosing to pop from the beginning and not the end (hence the `last=False` bit). With the OrderedDict, we can move any element within it to the front or back of the linked list, which allows us to pop items off in constant time. If you're either not familiar with Python, or not familiar with the underlying implementation of the `OrderedDict`, I agree that this definitely doesn't seem obvious.
Did this address what you were mentioning? Or did I misinterpret the question? LMK!
@@babybear-hq9yd Everything is good. Thank you so much for this video.
Thank you for a clear explanantion.
This was very tough for sure haha. I did it thanks to you! :)
she's a notorious one that's for sure :D
thank you that was really helpful and you explained it really well too
Thank you Azl J!!! 😊
Intuitively I solved this by using one dict and one DLL, where the DLL was ordered by frequency first and recency second, this way every time max capacity was reached I only had to remove the tail element. It got accepted but is only faster than 7%, is that fine or should I look at other approaches????
On the surface it seems sound to me. Remember that the most important piece about your interviews will be the conversations you have in getting to the answer! Being open to discussing pros & cons of your proposal(s) and keeping an open dialogue on how to continuously improve the code is what will get you over the line, *not* necessarily having the 99.99th percentile fastest code.
Hey please solve "The skyline problem" intuitively, it's hard to think about it. Thanks👍🏻
Hey Sumit, I'll have a look at that one. I think I've gone through it before but didn't make a video about it. Hang tight!
@@babybear-hq9yd Thanks👍🏻
What hardware sketchpad are you using? Thanks for the explanation!
it's the HUION 420 drawing pad. cheapest thing i could find on Amazon hahah
can you please do LRU Cache?
quite confident that one's outside my realm of expertise unfortunately
Just so you know, your implementation leaves empty defaultdicts behind. It still works, but causes the memory usage to grow over time, despite the cache capacity.
Nevermind, you address it later. Except it looks like you didn't note that you'll have to do it in put() as well.
thanks for the great explanation! Is there any way you could also do Minimum Difficulty of a Job Schedule(LC 1335)? haha
welcome! :) I've had that one requested a fair bit recently, but I don't have a tidy/working solution to it just yet. I'll see if I can get it done!
@@babybear-hq9yd thanks for the reply! I will look forward to it
I saw on leetcode there is a clever way to use a stack of stacks to solve this problem. Can you make a video explaining doing it that way?
I remember trying to go through that as well but it didn't make much sense to me at the time -- not familiar enough with it bud, sorry!
Great explanation, thank you
My pleasure 🙇♂️
West Virginia, mountain momma
Take me home, country roads..!😇
hahahhah, so happy someone caught it ;)
You don’t need an ordereddict, as regular dicts are already ordered as of Python 3.6 aren’t they? Good video though
i think you're right :)