LFU Cache - (Microsoft) : Explanation➕Live Coding
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- This is the 3rd Video on our Design Data Structure Playlist.
In this video we will try to solve a very good and famous and interesting Problem "LFU Cache". (Leetcode-460)
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : LFU Cache
Company Tags : Microsoft
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
Debate is over. This guy is the GOAT
Best Explaination for LFU😇
G.O.A.T TEACHER hai bhai 😎
Well yeah, as mentioned by others,
this guy is the G.O.A.T.
I believe by the end of this video explanation, I will be able to answer who is the real Goat of DSA on TH-cam 😅
Starting now
❤❤❤❤
Thanks again for the awesome explanation. You are very good at breaking down complex problems into easy solutions. One request can you also provide leetcode weekly contests explanations and how to approach questions during limited time since that is what interview OA simulate. This will help tremendously.
I will plan soon about that.
Thank you so much ❤️❤️
wow !! such a great explaination !! you deserve 100Million subscriber bro !!
Means a lot. Thank you so much 🙏😇❤️
the way you explained the question at the start of the video, i coded it myself, since i got a lot of intuition from the lru cache video, i did not have to watch this video full, only first 8-10 minutes were helpful
my AC code:
// Leetcode 460
class LFUCache {
public:
// we have to store frequency as well as maintain lru style for same frequency elements
map freq; // stores
unordered_map hash; // stores
int capacity;
LFUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if(hash.find(key)!=hash.end()){
// found
auto it = hash[key].first;
int f = hash[key].second;
int value = hash[key].first->second;
// since element is accessed, freq increases and also its position in
// dll will move forward (to the begin)
int new_f = f+1;
// erase old value
freq[f].erase(it);
// check if current freq dll becomes empty
if(freq[f].empty()) freq.erase(f);
// put the key with new_f to new list
freq[new_f].push_front({key, value});
// update the new address in hash
hash[key] = {freq[new_f].begin(), new_f};
return value;
}else{
// not found
return -1;
}
}
void put(int key, int value) {
// check if already exists
if(hash.find(key)!=hash.end()){
// found
auto it = hash[key].first;
int f = hash[key].second;
int oldValue = hash[key].first->second;
// since element is accessed, freq increases and also its position in
// dll will move forward (to the begin)
int new_f = f+1;
// erase the old value
freq[f].erase(it);
// check if current freq dll becomes empty
if(freq[f].empty()) freq.erase(f);
// put the key with new_f to new list, with new value provided
freq[new_f].push_front({key, value});
// update the new address in hash
hash[key] = {freq[new_f].begin(), new_f};
return;
}
// if not already exists
else{
if(hash.size() + 1 first;
int keyToBeRemoved = it->second.back().first;
// remove from freq
it->second.pop_back();
if(it->second.empty()) freq.erase(f);
// remove from hash
hash.erase(keyToBeRemoved);
// insert new element
freq[1].push_front({key, value});
hash[key] = {freq[1].begin(), 1};
}
}
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
I am so so happy to hear that. Keep it going 💪💪💪❤️
question bhut jyda tagda hai bhut sare corner case handle karne hai aur dimag me rkhne hai :)
ye single question se hi 1-2 round interview ek clear ho jyega pakka
maza aaya explanation bdhiya tha :)
Thank you so much 🙏❤️😇
superb brother..one small suggestion for beginners instead of freq.erase(freq.begin()->first); we can directly do a freq.erase(1); because of we always try to erase the one with lowest counter..other than this suggestion its really helpful. Good job
GOAT indeed✨🔥
very good exp brother. Keep the good work
Very nice & detail explanation.🥰❤
Thank you soo much because i saw many video but i understand from your video, concept as well as code both part are hard of this problem
Thank you so much.
Means a lot to me ❤️
Seriously 💥🔥🔥🔥
Thank you 😊
You're welcome 😊
Bhaiya Kamaal ho aap.Mik bhaiya zindabad!
Hello sir; we've been waiting for your videos
I will be back in no time. Soooon.
Mentioned here : th-cam.com/video/aG4fzsFir_0/w-d-xo.html
Thanks for trusting my channel
crazy explaination sir
Thank you so much 😇❤️
9:08 naughty ho rha h naughty😂
I got this same problem in my on campus online assignment for the company named avelera
which college??
Thanks a lot
The wait is over 🔥🔥🔥
Please start uploading contest videos atleast the 3rd and the 4th problem. if possible can you upload weekly contest 330?
Wait is over 😅
this is a nice video tbh
awesome
Best channel ever
Thank you 💓
good job sir
Thank you so much 😇❤️
Sir I'm confused about the size of cache. Everytime we insert at 1 , then only size is increased(size
since you are using ordered_map for Frequency, doesn't TC becomes O(logn) for accessing this frequency map?
The GOAT
Itni mehnat kaise karte ho bhai 🥺
🔥
❤🔥
Thanks Mazhar; very well explained. Will the time complexity be O(logN) where N is the number of operations; and this is mainly to maintain ordered map?
Explanation ❤
Thank you 😇❤️
Bro is God
Broooooo aap to hazaribagh se ho 😭😭 damnnnn mere Ghar ke pass
G.O.A.T
Sir pls upload binary tree cameras if possible.
Here is the Java solution
class LFUCache {
int capacity;
int curSize;
int minFrequency;
Map map;
Map freq;
public LFUCache(int capacity) {
this.capacity = capacity;
this.curSize = 0;
this.minFrequency = 0;
this.map = new HashMap();
this.freq = new HashMap();
}
public int get(int key) {
DLLNode curNode = map.get(key);
if(curNode == null)
return -1;
updateNode(curNode);
return curNode.val;
}
public void put(int key, int value) {
if(capacity == 0)
return;
if(map.containsKey(key)){
DLLNode curNode = map.get(key);
curNode.val = value;
updateNode(curNode);
}
else{
curSize++;
if(curSize > capacity){
DoubleLinkedList minFreqList = freq.get(minFrequency);
map.remove(minFreqList.tail.prev.key);
minFreqList.removeNode(minFreqList.tail.prev);
curSize--;
}
minFrequency = 1;
DLLNode newNode = new DLLNode(key, value);
DoubleLinkedList curList = freq.getOrDefault(1, new DoubleLinkedList());
curList.addNode(newNode);
freq.put(1, curList);
map.put(key, newNode);
}
}
public void updateNode(DLLNode curNode){
int curFreq = curNode.frequency;
DoubleLinkedList curList = freq.get(curFreq);
curList.removeNode(curNode);
if(curFreq == minFrequency && curList.listSize == 0){
minFrequency++;
}
curNode.frequency++;
DoubleLinkedList newList = freq.getOrDefault(curNode.frequency, new DoubleLinkedList());
newList.addNode(curNode);
freq.put(curNode.frequency, newList);
}
}
class DLLNode {
int key;
int val;
int frequency;
DLLNode prev;
DLLNode next;
DLLNode(int _key, int _val){
this.key = _key;
this.val = _val;
this.frequency = 1;
}
}
class DoubleLinkedList {
int listSize;
DLLNode head;
DLLNode tail;
DoubleLinkedList(){
this.listSize = 0;
this.head = new DLLNode(0,0);
this.tail = new DLLNode(0,0);
head.next = tail;
tail.prev = head;
}
public void addNode(DLLNode curNode){
DLLNode nextNode = head.next;
curNode.next = nextNode;
curNode.prev = head;
head.next = curNode;
nextNode.prev = curNode;
listSize++;
}
public void removeNode(DLLNode curNode){
DLLNode prevNode = curNode.prev;
DLLNode nextNode = curNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
listSize--;
}
}
❤️❤️❤️
man..sir how do you keep track of so many things at once?
😇❤️🙏 just trying my best to give the best content on youtube ❤️
😭😭😭
Are bhaiya mene LRU wali video dekhli or mereko laga ki wo aaj ka leetcode daily challenge hai
Or mai uska code LFU mai submit kr rha tha
Mereko laga test case galat hai
Or meri streak tut gyi 😭😭
Isses streak kaise tut skti hai ?
It won't break your streak.
You can still submit this code in LFU and the streak remains
Don’t worry, wrong submission doesn’t break streak.
One question what is the time complexity of both these functions?
Time complexity analysis:
1. get(int key):
- Searching for a key in the unordered_map `mp` takes O(1) time.
- Making the key most frequently used involves erasing and inserting elements in a list, which takes O(1) time since we have iterators.
- Overall time complexity: O(1).
2. put(int key, int value):
- Checking if the key exists in the unordered_map `mp` takes O(1) time.
- Updating the value and making the key most frequently used takes O(1) time.
- If the capacity is not reached, inserting a new element in the list takes O(1) time.
- If the capacity is reached, finding the least frequently used key and erasing it takes O(log n) time in the worst case due to the use of a map.
- Overall time complexity: O(1) for insertion if capacity is not reached, O(log n) for deletion if capacity is reached.
The overall time complexity of `get` and `put` operations is O(1) amortized time, where amortized time accounts for the occasional worst-case deletion in `put` when the capacity is reached.
Space complexity analysis:
1. The unordered_map `mp` stores the key and the iterator pointing to the corresponding vector, requiring O(n) space, where n is the number of keys.
2. The map `freq` stores the frequency and the list of vectors associated with each frequency, requiring O(n) space.
3. Each vector in the lists contains three integers, requiring O(3n) space.
4. Therefore, the overall space complexity is O(n).
Which application you are using to create the tutorial? It would be great to know.
Default note app on ipad
bhai gfg ki potd bhi start karo atleast hard wale ki video daalo
R a bhaiya kab aayoge jaldi ajao problem samajh nahi a raha
try to use english bro. helps world wide community.
I am waiting for your videos.
Maza nhi a ra questions m
bhaiya kha gye😐
Soon be back
th-cam.com/video/aG4fzsFir_0/w-d-xo.html
Bro juss forgot me