[LeetCode] Challenge log 146

Posted on | Edited on |
146. LRU Cache

Analysis:

Although the problem only asks for implementing two operaions. It actually requires more than that. The two obvious and a few hidden required operations are:

  1. get: access value by key in O(1) and update its “freshness”
  2. put: add (key, value) pair in data structure and set it to be the freshest
  3. delete: delete the least recently used pair
  4. update: update pair’s value and “freshness” = delete and move to end

First, if we want “get” to be done in O(1), hashing is a must. And we need to keep track of the “least recently used” element, hence a queue (FIFO) is considered. But if queue is used, updating the freshness of the pair will cost linear time, which is why a linklist should be used. So we can use hashing to map key to a node, where the value is saved. To update a node’s freshness from the linklist, we need to delete it from its original position, for which we need to not only know its next but also its pre — so we need to used double linklist! Finally, to delete the LRU from the hash table, we also need the key stored in the coresponding node. So now we have somthing like:

hash key 1 key 2 key 3 …
double linklist (k1, v1) (k2, v2) (k3, v3) …

Trick: Python has a class collections.OrderedDict(), which is a dict that keeps track of the insertion order…

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?

Example:

1
2
3
4
5
6
7
8
9
10
11
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
Soulution:
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
class ListNode:
    def __init__(self, k, v):
        self.next = None
        self.pre = None
        self.key = k
        self.val = v
        
class LRUCache:
    def __init__(self, capacity):
        self.map = {}
        self.cap = capacity
        self.head = h = ListNode(None, None)
        self.tail = t = ListNode(None, None)
        h.next = t
        t.pre = h
        
    def get(self, key):
        if key not in self.map:
            return -1
        else:
            node = self.map[key]
            self._delete(node)
            self._add(node)
            return node.val
        
    def put(self, key, value):
        # delete old key if exists
        if key in self.map: 
            node = self.map[key]
            self._delete(node)
            del self.map[key]            
        
        # delete LRU if full
        if len(self.map) == self.cap:
            lru = self.head.next
            self._delete(lru)
            del self.map[lru.key]
        
        # add it
        node = ListNode(key, value)
        self._add(node)
        self.map[key] = node

    def _delete(self, node):
        node.pre.next = node.next
        node.next.pre = node.pre
    
    def _add(self, node):
        n = self.tail
        p = self.tail.pre
        node.next = n
        node.pre = p
        p.next = node
        n.pre = node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# collections.OrderedDict()
class LRUCache:
    def __init__(self, capacity):
        self.map = collections.OrderedDict()
        self.cap = capacity
        
    def get(self, key):
        if key not in self.map:
            return -1
        else:
            self.map.move_to_end(key)
            return self.map[key]
        
    def put(self, key, value):
        if key in self.map: 
            self.map.move_to_end(key)
            self.map[key] = value
        else:
            if len(self.map) == self.cap:
                self.map.popitem(last = False)
            self.map[key] = value
0%