[LeetCode] 146. LRU Cache

Posted on | In

Problem

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.

The cache is initialized with a positive capacity.

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

Explanation

  1. We can use doubly linked list storing class node to achieve adding and removing in $O(1)$ time by using prev and next pointer. When we do get, we can use hashmap to achieve getting the value by key in $O(1)$ time.

  2. Besides put and get function, we also need to have remove and setHead function. If we run get on a node, then that node need to set it as head. If we have number of capacity node in our linked list, then if we put one more node, we need to remove the tail node.

Solution

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Node {
    int key;
    int val;
    Node prev = null;
    Node next = null;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    HashMap<Integer, Node> map = null;
    int cap;
    Node head = null;
    Node tail = null;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            remove(temp);
            setHead(temp);
            return temp.val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            remove(temp);
            temp.val = value;
            setHead(temp);
        } else {
            if (map.size() >= cap) {
                map.remove(tail.key);
                remove(tail);
            }
            Node temp = new Node(key, value);
            map.put(key, temp);
            setHead(temp);
        }
    }

    //remove a node
    private void remove(Node t) {
        if (t.prev != null) {
            t.prev.next = t.next;
        } else {
            head = t.next;
        }

        if (t.next != null) {
            t.next.prev = t.prev;
        } else {
            tail = t.prev;
        }
    }

    //set a node to be head
    private void setHead(Node t) {
        if (head != null) {
            head.prev = t;
        }
        t.next = head;
        t.prev = null;
        head = t;

        if (tail == null) {
            tail = head;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */