Leetcode: LRU Cache

Leetcode: LRU Cache

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.

The basic idea is to use LinkedHashMap, as it has property - capacity.

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
import java.util.LinkedHashMap; // need to import this

public class LRUCache {
    private LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        final int c = capacity; // make it final, so it can be used in inner class
        this.map = new LinkedHashMap<Integer, Integer>(c) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return this.size() > c;
            }
        };
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            int value = map.get(key);
      // why remove then put here? For LRU. ---- This is an ugly way, I know
            map.remove(key);
            map.put(key, value);
            return value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
        }
        map.put(key, value);
    }
}

Another solution with double linked list

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
public class LRUCache {
    private Map<Integer, LinkedNode> map;
    private int capacity;
    private LinkedNode head;
    private LinkedNode end;

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

    public int get(int key) {
        if (map.containsKey(key)) {
            LinkedNode node = map.get(key);
            removeNode(node);
            addNodeToHead(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        LinkedNode node = new LinkedNode(key, value);
        if (map.containsKey(key)) {
            removeNode(map.get(key));
            addNodeToHead(node);
        } else {
            if (map.size() >= capacity) {
                map.remove(end.key);
                removeNode(end);
            }
            addNodeToHead(node);
        }
        map.put(key, node);
    }


    private void removeNode(LinkedNode node) {
        LinkedNode prev = node.prev;
        LinkedNode next = node.next;
        if (prev == null && next == null) {
            head = end = null;
        } else if (prev == null) {
            head = next;
            head.prev = null;
        } else if (next == null) {
            end = prev;
            end.next = null;
        } else {
            prev.next = next;
            next.prev = prev;
        }
    }

    private void addNodeToHead(LinkedNode node) {
        if (head == null) {
            head = end = node;
            return;
        }
        head.prev = node;
        node.next = head;
        node.prev = null;
        head = node;
    }

    private static class LinkedNode {
        int value;
        int key;
        LinkedNode prev = null;
        LinkedNode next = null;

        LinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}