Implement LRU Cache | Implement LRU Cache using HashMap & Doubly Linked List | Programming Tutorials

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

Explained LRU Cache Implementation using HashMap and Doubly Linked List and it's Java Code.

In this tutorial, I have explained how to implement LRU cache get and put method in O(1) time complexity using HashMap and Doubly Linked List.

We have to design and implement a data structure for LRU (Least Recently Used) cache. It should support two operations get and put in O(1) time.

get(key) - Get the value if the key exists in a cache else returns -1.
put(key, value) - Insert the value if the key is already not present in a cache. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is Initialized with positive capacity.

LeetCode 30 Day Challenge
LeetCode Challenge Day 24 Question

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

Комментарии

Loved your explanation. Your tutorial is just awesome. Failed every other coding tutorial.

codingSpeedWithGK

Crystal Clear, Very nice explanation.

piyushsharma

very easy explanation of such complex problem.

sushmasinghSS

Well explained. Great work!! Keep it up :)

pmsb_

Is there use of doubly linked list here? I don't see it. Is the node itself by having next and prev, doing the job of the linkedlist?

lee

private int capacity;
HashMap<Integer, Integer> map=new HashMap<>();
Queue<Integer> queue=new LinkedList<>();
//HashMap<Integer, Integer> countMap=new HashMap<>();
public LRUCache(int capacity) {
this.capacity=capacity;
}

public int get(int key) {
if (map.containsKey(key)) {
if (queue.contains(key)) {
queue.remove(key);
queue.add(key);
return map.get(key);
}
}
return -1;
}

public void put(int key, int value) {

if(map.containsKey(key)){
queue.remove(key);
map.put(key, value);
queue.add(key);
}
else{
map.put(key, value);
queue.add(key);
}
}
else {
//when the cache reached the maximum capacity
//decide the LRU and remove from the map and mark it in queue and count map
if (map.containsKey(key)) {
queue.remove(key);
map.put(key, value);
queue.add(key);
} else {
int first = queue.remove();
map.remove(first);
map.put(key, value);
queue.add(key);
}
}
}

The easiest approach which i used to solve this problem and giving constant complexity for get and put operations.

praveenj

Can U plz upload the code, I am getting some errors so plz upload by night so that I can clear it asap

aishwaryahatti

Implement LRU Cache | Implement LRU Cache using HashMap & Doubly Linked List | Programming Tutorials

Implement LRU cache

Implement LRU Cache | Leetcode

L18. Implement LRU Cache

LRU Cache - Explanation, Java Implementation and Demo

LRU Cache - Twitch Interview Question - Leetcode 146

LRU Cache Implementation | Codewise explanation using Queue & Map | Java Code

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

Implement LRU cache with example

Leetcode 146. LRU Cache (most asked linked list problem)

Implement LRU Cache | Implement LRU Cache using HashMap & Doubly Linked List | Programming Tutor...

LRU Cache Implementation Explained Step-By-Step

#1 Coding Interview Question: LRU Cache Implementation(Logicmojo.com)

System Design - (P-1) - Java LRU Cache Implementation | Step-by-Step Tutorial with High-Level Design

LeetCode 146. LRU Cache (Algorithm Explained)

LRU cache implementation | How to implement LRU cache in Java

Implement LRU Cache | Explanation + Code | Optimized Code | Doubly LL + HashMap Approach

Linked List as Design Choice for LRU Cache

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

Implementing LRU - Georgia Tech HPCA Part 3

Implement LRU Cache | C++ and Java Clean and Short Implementation

LFU Cache - Leetcode 460 - Python

Implement LRU Cache in JavaScript 🔥

System Design | Distributed Cache | LRU Implementation | Systems design interview | Coding

Implement LRU Cache | SWE Interview #19