# Debugging this problem taught me a lesson on not to oversimplify

• After reading the idea of the top solution w/ doubly linked list and linked hashmap, I decided to implement on my own. But the debugging was painful because I got a lot of "Runtime Error"s without detailed explanation. Finally I found it was because of a usage of the hashmap.getOrDefault() method:

``````Node next = nodeMap.getOrDefault(freq + 1, new Node(curr, curr.next, freq + 1));
``````

The problem is, whether the map contains the key or not, the new Node will be initialized, which I didn't know. However, my Node constructor inserts the new node between the two Nodes as the first and second parameters because I do not want to insert it with an extra line of code every time I initialize a new node (because I am lazy). And this inserts a new Node in between even if I do have the node for the frequency.

It really took me long by printing a lot of details to find this bug. Anyway, I'll never oversimplify my code again in the future >_<.

Here's the full implementation:

``````    Map<Integer, Integer> kvStore;
Map<Integer, Integer> freqMap;
Map<Integer, Node> nodeMap;
int capacity;

public LFUCache(int capacity) {
kvStore = new HashMap<>();
freqMap = new HashMap<>();
nodeMap = new HashMap<>();
this.capacity = capacity;
}

public int get(int key) {
if (!kvStore.containsKey(key)) return -1;
int freq = freqMap.get(key);
increaseFreq(key, freq);
return kvStore.get(key);
}

public void put(int key, int value) {
if (capacity == 0) return;

if ((!kvStore.containsKey(key)) && kvStore.size() == capacity){ // remove the LFU key
int lfuKey = itr.next();
kvStore.remove(lfuKey);
freqMap.remove(lfuKey);
}
}

kvStore.put(key, value);
increaseFreq(key, freqMap.getOrDefault(key, 0));
}

void increaseFreq(int key, int freq) {
freqMap.put(key, freq + 1);
Node curr = nodeMap.get(freq);
if (curr == null) {
curr = new Node(null, head, 0);
nodeMap.put(0, curr);
}
Node next;
if (nodeMap.containsKey(freq + 1)) next = nodeMap.get(freq + 1);
else next = new Node(curr, curr.next, freq + 1);
curr.keys.remove(key);
if (curr.keys.isEmpty()) {
removeNode(curr);
}
nodeMap.put(freq + 1, next);
}

void removeNode(Node node) {
} else {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
}
}
nodeMap.remove(node.freq);
}

class Node {
Node prev;
Node next;
int freq;

Node(Node prev, Node next, int freq) {
this.freq = freq;
this.prev = prev;
this.next = next;
if (prev != null) {
prev.next = this;
}
if (next != null) {
next.prev = this;
}
}
}
}

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.