LRU cache | EP 22

Hi, I am Fraz.
I am Software Engineer working at Curefit and I love teaching.
This is my Channel where I upload content related to Interviews and my personal experiences.

My contact details

[facttecher]

Finally i understand the logic behind this problem.
I really like your way of explaination .
This type of explaination I don't get anywhere.
Keep it up sir ji.

[ayushbhagwat]

It's giving TLE 21/22 Test cases passed. I even tried using unordered_map but still no effect.
Last executed input:
["LRUCache", "get", "get", "put", "get", "put", "put", "put", "put", "get", "put"]
[[1], [6], [8], [12, 1], [2], [15, 11], [5, 2], [1, 15], [4, 2], [5], [15, 15]]

[dpThePlaya]

done for this weekend, looking forward to next. Thank you sir.

[desihiphop]

Bhiaya poori playlist ka sabse accha question laga pehle bhe kr rakha tha but ni kr paaya is baar but ab acche se smjh gya Hero ho bhaiya aap !!!🖤🖤

[Wanna_be_]

1. BRUTE FORCE APPROACH(Using Queue + HashMap):-

class LRUCache {
public:
unordered_map <int, int> m, cnt;
queue <int> q;
int n;
LRUCache(int capacity){
n = capacity;
}
int get(int key) {
if (cnt.find(key) == cnt.end())
return -1;
q.push(key);
cnt[key]++;
return m[key];
}
void put(int key, int value) {
q.push(key);
cnt[key]++;
m[key] = value;
while (cnt.size() > n) {
int cur = q.front(); q.pop();
if (cnt[cur]-- == 1)
cnt.erase(cur);
}
}
};

// Time Complexity = O(n+m)
// Space Complexity = O(n+m)


2. OPTIMIZED APPROACH(Using DLL + HashMap) - By Fraz Bhaiya (from this lecture):-

class LRUCache {
public:
unordered_map<int, int> m;
unordered_map<int, list<int> :: iterator> address;
list<int> l;
int cap;
int siz;

LRUCache(int capacity) {
cap = capacity;
siz = 0;
}

int get(int key) {
if(m.find(key) == m.end()) return -1;
auto it = address[key];
l.erase(it);
address.erase(key);
l.push_front(key);
address[key] = l.begin();
return m[key];
}

void put(int key, int value) {
if(m.find(key) != m.end()){
auto it = address[key];
l.erase(it);
address.erase(key);
m.erase(key);
siz--;
}

if(siz == cap){
int del = l.back();
l.pop_back();
address.erase(del);
m.erase(del);
siz--;
}

siz++;
l.push_front(key);
address[key] = l.begin();
m[key] = value;
}
};

// Time Complexity = O(1)
// Space Complexity = O(Capacity)

Enjoy Guys !!! ❤😉
I wrote here for revision purpose in future but you can use too for revision :)
And Thank to Fraz Bhaiya 🙏🥰❣🔥for whole content :)

[mohdsaadalikhan]

time: o(1) average case, o(n) worst case (as in unordered map, collisions may increase the time for search or insert to o(n) )
space: o(n)
correct me if i am wrong?

[mgdesire]

finally S2 done...looking forward Bhaiya can't wait for upcoming season.

[baap]

Sir your videos are absolute gold.
Keep posting.
I am in final year.
Wished I was born 2-3 years later

[abhayrai]

Bhaiya aab aap ese ese educational videos kyu nhi dal rhe missing those days jb ache ache ques solve krwate the aap kafi easily .... Plz laut aao purane wale bhaiya 😍🤗

[HarshRaj-kpgk]

sir, please make a video on (computer network) preparation in 3 days for placement
sir, "you forgot it this subject to make a video "
its humble request sir please make a video as soon as possible

[vivekmahindrakar]

Can we use Stacks where the most recently used is the top and lru is at the bottom???

[shashankpandey]

Both get() and put() will have time complexity of O(n), because you are using erase() which take O(n) time
Random Access is not allowed in list
try to implement in O(1) as asked in question @frazmohammad
Thanks

[devendrabhuarya]

class LRUCache {
public:
unordered_map<int, int> values;
unordered_map<int, list<int>::iterator >m;
list<int> l;
int capacity, size;
LRUCache(int capacity) {
this->capacity=capacity;
size=0;
}

int get(int key) {
if(m.find(key)==m.end()) return -1;
auto it=m[key];
l.erase(it);
l.push_front(key);
m[key]=l.begin();
return values[key];
}

void put(int key, int value) {
if(m.find(key)!=m.end()) {
auto it=m[key];
l.erase(it);
l.push_front(key);
m[key]=l.begin();
values[key]=value;
return;
}
if(size<capacity) {
l.push_front(key);
m[key]=l.begin();
values[key]=value;
size++;
return;
}
auto it=l.back();
l.pop_back();
m.erase(it);
values.erase(it);
l.push_front(key);
m[key]=l.begin();
values[key]=value;
}
};

[krishnaradhey]

fraz bhaiya if i am implementing this question in the opposite of this approach means that for least recently used i am putting nodes on right side end
and for most recently used (to be pop) on the left side end
IT IS GIVING TLE BY THIS REVERSE APPROACH ???CAN ANYONE EXPLAIN WHY

[editorera]

Thnx bhaiya
In series m linked list complete ho jaega na overall I mean

[tech_wizard]

By when you will upload entire playlist

[louistomlinson]

if anybody is wondering how will be the java code, here it is

class LRUCache {

HashMap<Integer, Node> map;
Node head;
Node tail;
int capacity;
public LRUCache(int capacity) {
head = new Node(0, 0);
tail = new Node(0, 0);
this.capacity = capacity;
map = new HashMap<>();
head.next = tail;
tail.prev = head;
}

public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
delete(node);
insert(node);
return node.value;
} else {
return -1;
}
}

public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
map.put(key, node);
delete(node);
insert(node);
} else if (map.size() < capacity) {
Node newNode = new Node(key, value);
map.put(key, newNode);
insert(newNode);
} else {
Node newNode = new Node(key, value);
Node toDelete = tail.prev;
map.remove(toDelete.key);
delete(toDelete);
insert(newNode);
map.put(key, newNode);
}
}

private void delete(Node node) {
Node prev = node.prev;
Node next = node.next;

prev.next = next;
next.prev = prev;
}

private void insert(Node node) {
Node headNext = head.next;
head.next = node;
node.prev = head;
node.next = headNext;
headNext.prev = node;
}

}

class Node {
int key;
int value;
Node next;
Node prev;

public Node(int key, int value) {
this.key = key;
this.value = value;
next = prev = null;
}
}

[rishupatel]

Is anyone getting TLE For this solution

[Sai-fptu]

Overall linked list ka kitne videos ayenge bhaiya?
Btw Awesome teaching 🔥🔥

[deepakprajapat]

Sir STL full concept ka uper aap video kab upload karoge
Plzzzz