304 North Cardinal St.
Dorchester Center, MA 02124

LRU Cache LeetCode Solution

Problem – LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the `LRUCache` class:

• `LRUCache(int capacity)` Initialize the LRU cache with positive size `capacity`.
• `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`.
• `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, evict the least recently used key.

The functions `get` and `put` must each run in `O(1)` average time complexity.

Example 1:

``````Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
``````

Constraints:

• `1 <= capacity <= 3000`
• `0 <= key <= 104`
• `0 <= value <= 105`
• At most `2 * 105` calls will be made to `get` and `put`.

LRU Cache LeetCode Solution in Java

``````import java.util.Hashtable;

public class LRUCache {

int key;
int value;
}

/**
*/

}

/**
* Remove an existing node from the linked list.
*/

pre.post = post;
post.pre = pre;
}

/**
* Move certain node in between to the head.
*/
this.removeNode(node);
}

// pop the current tail.
this.removeNode(res);
return res;
}

private int count;
private int capacity;

public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;

tail.post = null;

}

public int get(int key) {

if(node == null){
return -1; // should raise exception here.
}

// move the accessed node to the head;

return node.value;
}

public void put(int key, int value) {

if(node == null){

newNode.key = key;
newNode.value = value;

this.cache.put(key, newNode);

++count;

if(count > capacity){
// pop the tail
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
}
}

}
``````

LRU Cache LeetCode Solution in Python

``````class Node:
def __init__(self, k, v):
self.key = k
self.val = v
self.prev = None
self.next = None

class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.dic = dict()
self.tail = Node(0, 0)

def get(self, key):
if key in self.dic:
n = self.dic[key]
self._remove(n)
return n.val
return -1

def set(self, key, value):
if key in self.dic:
self._remove(self.dic[key])
n = Node(key, value)
self.dic[key] = n
if len(self.dic) > self.capacity:
self._remove(n)
del self.dic[n.key]

def _remove(self, node):
p = node.prev
n = node.next
p.next = n
n.prev = p

p = self.tail.prev
p.next = node
self.tail.prev = node
node.prev = p
node.next = self.tail
``````

LRU Cache LeetCode Solution in C++

``````class LRUCache{
size_t m_capacity;
unordered_map<int,  list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
list<pair<int, int>> m_list;                               //m_list_iter->first: key, m_list_iter->second: value;
public:
LRUCache(size_t capacity):m_capacity(capacity) {
}
int get(int key) {
auto found_iter = m_map.find(key);
if (found_iter == m_map.end()) //key doesn't exist
return -1;
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
return found_iter->second->second;                         //return value of the node
}
void set(int key, int value) {
auto found_iter = m_map.find(key);
if (found_iter != m_map.end()) //key exists
{
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
found_iter->second->second = value;                        //update value of the node
return;
}
if (m_map.size() == m_capacity) //reached capacity
{
int key_to_del = m_list.back().first;
m_list.pop_back();            //remove node in list;
m_map.erase(key_to_del);      //remove key in map
}
m_list.emplace_front(key, value);  //create new node in list
m_map[key] = m_list.begin();       //create correspondence between key and node
}
};
``````
LRU Cache LeetCode Solution Review:

In our experience, we suggest you solve this LRU Cache LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the LRU Cache LeetCode Solution

Find on LeetCode

Conclusion:

I hope this LRU Cache LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions