LFU Cache LeetCode solution in Java

1
class LFUCache {
2

3
  final int capacity;
4
  int curSize;
5
  int minFrequency;
6
  Map<Integer, DLLNode> cache;
7
  Map<Integer, DoubleLinkedList> frequencyMap;
8

9
  /*.*/
10
  /*
11
   * @param capacity: total capacity of LFU Cache
12
   * @param curSize: current size of LFU cache
13
   * @param minFrequency: frequency of the last linked list (the minimum frequency of entire LFU cache)
14
   * @param cache: a hash map that has key to Node mapping, which used for storing all nodes by their keys
15
   * @param frequencyMap: a hash map that has key to linked list mapping, which used for storing all
16
   * double linked list by their frequencies
17
   * */
18
  public LFUCache(int capacity) {
19
    this.capacity = capacity;
20
    this.curSize = 0;
21
    this.minFrequency = 0;
22

23
    this.cache = new HashMap<>();
24
    this.frequencyMap = new HashMap<>();
25
  }
26

27
  /** get node value by key, and then update node frequency as well as relocate that node * */
28
  public int get(int key) {
29
    DLLNode curNode = cache.get(key);
30
    if (curNode == null) {
31
      return -1;
32
    }
33
    updateNode(curNode);
34
    return curNode.val;
35
  }
36

37
  /**
38
   * add new node into LFU cache, as well as double linked list condition 1: if LFU cache has input
39
   * key, update node value and node position in list condition 2: if LFU cache does NOT have input
40
   * key - sub condition 1: if LFU cache does NOT have enough space, remove the Least Recent Used
41
   * node in minimum frequency list, then add new node - sub condition 2: if LFU cache has enough
42
   * space, add new node directly *
43
   */
44
  public void put(int key, int value) {
45
    // corner case: check cache capacity initialization
46
    if (capacity == 0) {
47
      return;
48
    }
49

50
    if (cache.containsKey(key)) {
51
      DLLNode curNode = cache.get(key);
52
      curNode.val = value;
53
      updateNode(curNode);
54
    } else {
55
      curSize++;
56
      if (curSize > capacity) {
57
        // get minimum frequency list
58
        DoubleLinkedList minFreqList = frequencyMap.get(minFrequency);
59
        cache.remove(minFreqList.tail.prev.key);
60
        minFreqList.removeNode(minFreqList.tail.prev);
61
        curSize--;
62
      }
63
      // reset min frequency to 1 because of adding new node
64
      minFrequency = 1;
65
      DLLNode newNode = new DLLNode(key, value);
66

67
      // get the list with frequency 1, and then add new node into the list, as well as into LFU
68
      // cache
69
      DoubleLinkedList curList = frequencyMap.getOrDefault(1, new DoubleLinkedList());
70
      curList.addNode(newNode);
71
      frequencyMap.put(1, curList);
72
      cache.put(key, newNode);
73
    }
74
  }
75

76
  public void updateNode(DLLNode curNode) {
77
    int curFreq = curNode.frequency;
78
    DoubleLinkedList curList = frequencyMap.get(curFreq);
79
    curList.removeNode(curNode);
80

81
    // if current list the the last list which has lowest frequency and current node is the only
82
    // node in that list
83
    // we need to remove the entire list and then increase min frequency value by 1
84
    if (curFreq == minFrequency && curList.listSize == 0) {
85
      minFrequency++;
86
    }
87

88
    curNode.frequency++;
89
    // add current node to another list has current frequency + 1,
90
    // if we do not have the list with this frequency, initialize it
91
    DoubleLinkedList newList = frequencyMap.getOrDefault(curNode.frequency, new DoubleLinkedList());
92
    newList.addNode(curNode);
93
    frequencyMap.put(curNode.frequency, newList);
94
  }
95

96
  /*
97
   * @param key: node key
98
   * @param val: node value
99
   * @param frequency: frequency count of current node
100
   * (all nodes connected in same double linked list has same frequency)
101
   * @param prev: previous pointer of current node
102
   * @param next: next pointer of current node
103
   * */
104
  class DLLNode {
105
    int key;
106
    int val;
107
    int frequency;
108
    DLLNode prev;
109
    DLLNode next;
110

111
    public DLLNode(int key, int val) {
112
      this.key = key;
113
      this.val = val;
114
      this.frequency = 1;
115
    }
116
  }
117

118
  /*
119
   * @param listSize: current size of double linked list
120
   * @param head: head node of double linked list
121
   * @param tail: tail node of double linked list
122
   * */
123
  class DoubleLinkedList {
124
    int listSize;
125
    DLLNode head;
126
    DLLNode tail;
127

128
    public DoubleLinkedList() {
129
      this.listSize = 0;
130
      this.head = new DLLNode(0, 0);
131
      this.tail = new DLLNode(0, 0);
132
      head.next = tail;
133
      tail.prev = head;
134
    }
135

136
    /** add new node into head of list and increase list size by 1 * */
137
    public void addNode(DLLNode curNode) {
138
      DLLNode nextNode = head.next;
139
      curNode.next = nextNode;
140
      curNode.prev = head;
141
      head.next = curNode;
142
      nextNode.prev = curNode;
143
      listSize++;
144
    }
145

146
    /** remove input node and decrease list size by 1* */
147
    public void removeNode(DLLNode curNode) {
148
      DLLNode prevNode = curNode.prev;
149
      DLLNode nextNode = curNode.next;
150
      prevNode.next = nextNode;
151
      nextNode.prev = prevNode;
152
      listSize--;
153
    }
154
  }
155
}
156

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