LFU Cache - (Microsoft) : Explanation➕Live Coding

[@nagmakhan672]

Debate is over. This guy is the GOAT

[@shikharpandya4927]

Best Explaination for LFU😇

[@souravjoshi2293]

Well yeah, as mentioned by others, this guy is the G.O.A.T.

[@Raj10185]

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

[@codestorywithMIK]

Thank you so much 🙏❤️😇

[@PrinceKumar-eq3px]

wow !! such a great explaination !! you deserve 100Million subscriber bro !!

[@codestorywithMIK]

Means a lot. Thank you so much 🙏😇❤️

[@iWontFakeIt]

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

[@iWontFakeIt]

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); */

[@codestorywithMIK]

I am so so happy to hear that. Keep it going 💪💪💪❤️

[@devangsehgal]

G.O.A.T TEACHER hai bhai 😎

[@UECAshutoshKumar]

Thank you 😊

[@codestorywithMIK]

You're welcome 😊

[@vishalkurve93]

Bhaiya Kamaal ho aap.Mik bhaiya zindabad!

[@saurabhN1393]

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.

[@codestorywithMIK]

I will plan soon about that. Thank you so much ❤️❤️

[@abhinavnarang4369]

very good exp brother. Keep the good work

[@snehagoyal4978]

GOAT indeed✨🔥

[@divyabharathi5324]

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

[@shabananoor9423]

Seriously 💥🔥🔥🔥

[@lazyhead1276]

crazy explaination sir

[@codestorywithMIK]

Thank you so much 😇❤️

[@SONALIKUMARI-is9jc]

Hello sir; we've been waiting for your videos

[@codestorywithMIK]

I will be back in no time. Soooon. Mentioned here : kzbin.info/www/bejne/l3iXl62pe86llZI Thanks for trusting my channel

[@expert_solver]

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

[@codestorywithMIK]

Thank you so much. Means a lot to me ❤️

[@souravjoshi2293]

The wait is over 🔥🔥🔥

[@ipranavprashant]

9:08 naughty ho rha h naughty😂

[@tutuimam3381]

Thanks a lot

[@nagmakhan672]

I believe by the end of this video explanation, I will be able to answer who is the real Goat of DSA on KZbin 😅 Starting now

[@mudassarnazar1663]

❤❤❤❤

[@Rider12374]

>>G.O.A.T Guy........

[@thekindspill]

Best channel ever

[@nishantdehariya5769]

awesome

[@rishabhjain5281]

I got this same problem in my on campus online assignment for the company named avelera

[@prathamjiwnani6419]

which college??

[@niteshk0487]

Wait is over 😅

[@AdritoDey]

Please start uploading contest videos atleast the 3rd and the 4th problem. if possible can you upload weekly contest 330?

[@karthikeysharma9161]

🔥

[@babluvishwakarma9898]

good job sir

[@codestorywithMIK]

Thank you so much 😇❤️

[@shabananoor9423]

The GOAT

[@vineetkumar2899]

Thank you 💓

[@gurnishsingh257]

this is a nice video tbh

[@aftereffectstraining7668]

❤🔥

[@AlishaKhan-ww3io]

G.O.A.T

[@gulshanmathur3738]

Again nice explanation, how did you understand this enormous problem?

[@monjuralam7346]

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?

[@ektuhaso]

Explanation ❤

[@codestorywithMIK]

Thank you 😇❤️

[@souravjoshi2293]

Itni mehnat kaise karte ho bhai 🥺

[@pallabghosh3840]

Sir I'm confused about the size of cache. Everytime we insert at 1 , then only size is increased(size

[@AkashKumarTiwary-u4b]

Bro is God

[@AkashKumarTiwary-u4b]

Broooooo aap to hazaribagh se ho 😭😭 damnnnn mere Ghar ke pass

[@AryanTomar_2025]

Sir pls upload binary tree cameras if possible.

[@mohanmanis]

Which application you are using to create the tutorial? It would be great to know.

[@codestorywithMIK]

Default note app on ipad

[@invinciblearmyvlogsshorts7911]

man..sir how do you keep track of so many things at once?

[@codestorywithMIK]

😇❤️🙏 just trying my best to give the best content on youtube ❤️

[@JJ-tp2dd]

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

[@codestorywithMIK]

❤️❤️❤️

[@pradipacharjee4915]

For the frequency map , you should consider unordered_map. Ordered map will not help to achive o(1)

[@abhinavnarang4369]

One question what is the time complexity of both these functions?

[@codestorywithMIK]

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

[@MakeuPerfect]

R a bhaiya kab aayoge jaldi ajao problem samajh nahi a raha

[@ec039venom4]

I am waiting for your videos. Maza nhi a ra questions m

[@avinashvishwakarma6488]

bhai gfg ki potd bhi start karo atleast hard wale ki video daalo

[@divyangdheer7292]

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

[@shashwatchawla]

Isses streak kaise tut skti hai ?

[@souravjoshi2293]

It won't break your streak. You can still submit this code in LFU and the streak remains

[@codestorywithMIK]

Don’t worry, wrong submission doesn’t break streak.

[@manishasaini307]

bhaiya kha gye😐

[@codestorywithMIK]

Soon be back kzbin.info/www/bejne/l3iXl62pe86llZI

[@mohitsinha1994]

since you are using ordered_map for Frequency, doesn't TC becomes O(logn) for accessing this frequency map?

[@nishant7083]

Bro juss forgot me

[@MitaliNeerPatel]

try to use english bro. helps world wide community.