146. LRU Cache

  • 16.7%

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:

Could you do both operations in O(1) time complexity?

1
2
3
4
5
6
7
8
9
10
11
12
13
Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

https://discuss.leetcode.com/topic/6812/c-11-code-74ms-hash-table-list

C++11 code 74ms - Hash table + List

There is a similar example in Java, but I wanted to share my solution using the new C++11 unordered_map and a list. The good thing about lists is that iterators are never invalidated by modifiers (unless erasing the element itself). This way, we can store the iterator to the corresponding LRU queue in the values of the hash map. Since using erase on a list with an iterator takes constant time, all operations of the LRU cache run in constant time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class LRUCache {
public:
LRUCache(int capacity) : _capacity(capacity) {}

int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
touch(it);
return it->second.first;
}

void set(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) touch(it);
else {
if (cache.size() == _capacity) {
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
}
cache[key] = { value, used.begin() };
}

private:
typedef list<int> LI;
typedef pair<int, LI::iterator> PII;
typedef unordered_map<int, PII> HIPII;

void touch(HIPII::iterator it) {
int key = it->first;
used.erase(it->second.second);
used.push_front(key);
it->second.second = used.begin();
}

HIPII cache;
LI used;
int _capacity;
};

https://discuss.leetcode.com/topic/25792/clean-short-standard-c-solution-not-writing-c-in-c-like-all-other-lengthy-ones

Clean Short Standard C++ solution – NOT writing C in C++ like all other lengthy ones

I saw so many (or all) “C++” solutions posted here were not written in C++ at all. For those 200-line solutions, I don’t see the point in implementing a double-linked-list by themselves.

If you are writing C++, please use STL!

The code below is way cleaner, shorter and easier to read than most other C++ solutions posted here.
And above all, it was written in a standard C++ way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
}
};

https://discuss.leetcode.com/topic/4324/accepted-c-solution-296-ms

Accepted C++ solution, 296 ms

Solution is unusual - combination of 2 data structures - hash map and linked list.
Algorithm:

hash map holds iterators to linked list

linked list holds key and value, key to access hash map items

when item is accessed, it’s promoted - moved to the tail of the list - O(1) operation

when item should be removed, we remove head of the list - O(1) operation

when item is not promoted long time, it’s moved to the head of the list automatically

get() - O(1) performance, set() - O(1) performance

{

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class LRUCache{
private:
struct item_t{
int key, val;
item_t(int k, int v) :key(k), val(v){}
};
typedef list<item_t> list_t;
typedef unordered_map<int, list_t::iterator> map_t;

map_t m_map;
list_t m_list;
int m_capacity;
public:
LRUCache(int capacity) : m_capacity(capacity) {
}
int get(int key) {
map_t::iterator i = m_map.find(key);
if (i == m_map.end()) return -1;
m_map[key] = promote(i->second);
return m_map[key]->val;
}
void set(int key, int value) {
map_t::iterator i = m_map.find(key);
if (i != m_map.end()){
m_map[key] = promote(i->second);
m_map[key]->val = value;
}
else {
if (m_map.size() < m_capacity){
m_map[key] = m_list.insert(m_list.end(), item_t(key, value));
}
else {
m_map.erase(m_list.front().key);
m_list.pop_front();
m_map[key] = m_list.insert(m_list.end(), item_t(key, value));
}
}
}
list_t::iterator promote(list_t::iterator i){
list_t::iterator inew = m_list.insert(m_list.end(), *i);
m_list.erase(i);
return inew;
}
};
}

btw LeetCode, it was really hard to insert this code, after pressing {} button, class was improperly formatted. I inserted additional braces around class.


https://discuss.leetcode.com/topic/12262/o-1-unordered_map-list-splice

O(1) unordered_map + list + splice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class LRUCache {
private:
// A list of (key, value) pairs
list<pair<int, int>> items;
// Map items to iterators (pointers) to list nodes
unordered_map<int, list<pair<int, int>>::iterator> cache;
// The capacity of the list
int capacity;

public:
LRUCache(int capacity) : capacity(capacity) {}

int get(int key) {
// If key is not found in hash map, return -1
if (cache.find(key) == cache.end())
return -1;
// Move the (key, value) pair to the beginning of the list
items.splice(items.begin(), items, cache[key]);
return cache[key]->second;
}

void set(int key, int value) {
// The key is not in the hash table
if (cache.find(key) == cache.end()) {
// If the cache is full then delete the least recently
// used item, which is at the end of the list
if (items.size() == capacity) {
cache.erase(items.back().first);
items.pop_back();
}
items.push_front(make_pair(key, value));
cache[key] = items.begin();
} else {
// Update the value associated with the key
cache[key]->second = value;
// Move the (key, value) pair to the beginning of the list
items.splice(items.begin(), items, cache[key]);
}
}
}

https://discuss.leetcode.com/topic/14591/python-dict-double-linkedlist

Python Dict + Double LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head

def get(self, key):
if key in self.dic:
n = self.dic[key]
self._remove(n)
self._add(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._add(n)
self.dic[key] = n
if len(self.dic) > self.capacity:
n = self.head.next
self._remove(n)
del self.dic[n.key]

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

def _add(self, node):
p = self.tail.prev
p.next = node
self.tail.prev = node
node.prev = p
node.next = self.tail

https://discuss.leetcode.com/topic/24757/python-concise-solution-with-comments-using-ordereddict

Python concise solution with comments (Using OrderedDict).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def __init__(self, capacity):
self.dic = collections.OrderedDict()
self.remain = capacity

def get(self, key):
if key not in self.dic:
return -1
v = self.dic.pop(key)
self.dic[key] = v # set key as the newest one
return v

def set(self, key, value):
if key in self.dic:
self.dic.pop(key)
else:
if self.remain > 0:
self.remain -= 1
else: # self.dic is full
self.dic.popitem(last=False)
self.dic[key] = value
谢谢你,可爱的朋友。