LRU cache | Leetcode #146

Показать описание

This video explains a very important interview programming question which is to find how to implement LRU cache,i.e., the least recently used paging algorithm. I have shown this by using proper examples and CODE of how we can implement LRU cache in just O(1) TIME. The full explanation for this topic is present on IMPLEMENT LRU CACHE video and its LINK is given below in description. CODE LINK is given below as well. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

Рекомендации по теме

Комментарии

Best solution! I was stuck at that exact question on how to refresh position so that even while get() operation we push the element to the front. Thank you!!!!

pratikjain

In 2:02 shouldn't get(5) returns -1, since 5 is not present, only during put(5), the function works as explained.

sreejiths

For erasing from list, it requires O(n). So, i think doubly ll will perform better as explained in your last video.

riyabharti

Thank you so much for this video. You really put in all your efforts to make things simpler for us.

amc

just a little clarification: search is O(1) but when we are modifying the linked list by bringing the requested node from somewhere in middle to the front. time complexity there should be O(n). isn't it?

shritishaw

Well explained. I got the right solutions of my doubt after spending hours in searching

pragyasingh

sir, please make video on complete road map of cp. from scratch to end, from where to start and which topics to cover and from which resources?

yashgoswami

Did anyone notice the Leet Code logo in the video thumbnail? 😂 Naughty techdose. Keep it up! 😂

iknoorsingh

I understand a lot 😇😊.. with code as well theory .. thanks you sir to make a such beautiful presentation

kunalsoni

Hello, thanks for such a nice explanation.
I had one doubt - why are we taking a list with pair for cache? Does it imply page number and address?

akhilmehta

Great video, a small doubt though.... list.erase() function is having linear TC. So how this is O(q), where q is number of queries? Should not it be O(nq)?

parikshitgune

I really liked your videos, can you please make videos on dynamic programming

techfusionwithamit

I was about to search LRU cache Tech dose then notification appeared what a coincidence haha :)

yashpreetbathla

Hi, just wanted to understand how this will make sure that it storing address as value in the map in below lines
unordered_map<int, list<pair<int, int>>::iterator> mymap;

AnilGupta-ivrz

can u plz tell me why we are taking list as pairs?

dhanashreegodase

I found that it is not working with deque but working with list... because the iterators get invalidated in deque after we remove or insert in the middle so they are not correct anymore.. but they will work in case of list... so whenever we want to implement a doubly linked list its much better to use list instead of deque!!

HimanshuSharma-tmms

one question bhaiya, The time complexity of searching in map is log(n) isn't it, then how we can use it as o(1) Yes Got it we considered it as o(1). If any optimal solution is there then please send it here

empiregaming

how can you say that erase function of deque work in O(1) time

ShubhamKumar-rtnb

class LRUCache {

int capacity;
LinkedHashMap<Integer, Integer> hm ;

public LRUCache(int capacity) {
this.capacity = capacity;
hm = new LinkedHashMap<Integer, Integer>(capacity);
}

public int get(int key) {
int value;
if(hm.containsKey(key)){
value = hm.get(key);
hm.remove(key);
hm.put(key, value);
return value;
}

else
return -1;
}

public void put(int key, int value) {
if(hm.containsKey(key))
{
hm.remove(key);
}
else if(hm.size()==capacity)
{
Iterator<Integer> iterator = hm.keySet().iterator();

int firstKey = iterator.next();
hm.remove(firstKey);

}
hm.put(key, value);

}
}

it is still slower any idea why ? using hashset, how much is your solution beat time?

ShubhamSharma

What does :: iterator do in the hash map?

harsh_dn

LRU cache | Leetcode #146

LRU Cache - Twitch Interview Question - Leetcode 146

LeetCode 146. LRU Cache (Algorithm Explained)

LRU cache | Leetcode #146

LRU cache | Live Coding with Explanation | Leetcode #146

Разбор задачи с интервью. Leetcode 146. LRU Cache

LRU Cache - 146. LeetCode - Java

LRU Cache | Brute Force | Optimal | Detailed | Leetcode 146

L18. Implement LRU Cache

Implement LRU Cache | Leetcode

Разбор задачи 146 leetcode.com LRU Cache. Решение на C++

[Java] Leetcode 146. LRU Cache [Design #1]

LRU Cache | Leetcode 146

Google Engineer Explains - LeetCode #146 - LRU Cache - Solution (Python)

Implement LRU cache

Implement An LRU Cache - The LRU Cache Eviction Policy ('LRU Cache' on LeetCode)

LRU Cache Walkthrough (Leetcode #146)

LRU Cache | (C++, Java, Python) |30 day Challenge | Day 24 | LeetCode #146

146. LRU Cache - Day 18/31 Leetcode July Challenge

Design LRU Cache Data Sturcture | LeetCode 146. LRU Cache | Least Recently Used Cache (LRU Cache)

LeetCode | 146 LRU Cache | C++ | Explanation

Software Engineer/Developer Interview Question: 146. LRU Cache

LeetCode 146 - Medium - LRU Cache

[SOLVED!] LRU Cache - LeetCode 146 - Java

Code with Jess - Leetcode #146 LRUCache