Algorithm

LintCode/LRU Cache

Problem Summary

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

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

  • set(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.

Solution

We can use linked list together with unordered map to solve this problem.

First, we use a linked list L to record pairs of keys and values. Each time we insert a new pair (key,value), we use the map to mark the position of it.

Then, for each get(key) operation, we can locate the pair (key,value) using the map in O(1) time. We also need to move the pair to the beginning of the linked list, since it is just used. Don’t forget to modify map[key] as the position of pair (key,value) changed.

As for the set(key,value) operation,

  1. If (key,previous_value) already exits in the list, we erase it and insert the new pair.
  2. If key is not already present, we need to check the capacity first. If the cache has reached its capacity, we erase the least recently used item, i.e. the pair at the end of the linked list. Then we insert the new pair to the beginning.
    And of course, we need to maintain the map in the above process.

The time complexities of get and set operations are both O(1), since the map is unordered.

Code

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <list>
class LRUCache {
public:
    int cap, used;
    list<pair<int,int> > l;
    unordered_map<int,list<pair<int,int> >::iterator> position;
    /*
    * @param capacity: An integer
    */
    LRUCache(int capacity) {
        cap = capacity;
        used = 0;
    }
    /*
     * @param key: An integer
     * @return: An integer
     */
    int get(int key) {
        if(position.count(key) == 0)
            return -1;
        else
        {
            list<pair<int,int> >::iterator it = position[key];
            int res = (*it).second;
            if (it != l.begin())
            {
                l.insert(l.begin(),make_pair(key,res));
                l.erase(it);
                position[key] = l.begin();
            }
            return res;
        }
    }
    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    void set(int key, int value) {
        if (cap <= 0)
            return;
        if (position.count(key) == 0)
        {
            if (used >= cap)
            {
                list<pair<int,int> >::iterator it = l.end();
                --it;
                position.erase((*it).first);
                l.erase(it);
            }
            else
                ++used;
        }
        else
        {
            list<pair<int,int> >::iterator it = position[key];
            l.erase(it);
        }
        l.insert(l.begin(),make_pair(key,value));
        position[key] = l.begin();
    }
};