Debugging this problem taught me a lesson on not to oversimplify

  • 0

    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,, 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;
        Node head;
        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
                Iterator<Integer> itr = head.keys.iterator();
                int lfuKey =;
                if (head.keys.isEmpty()) {
            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);
                head = curr;
                nodeMap.put(0, curr);
            Node next;
            if (nodeMap.containsKey(freq + 1)) next = nodeMap.get(freq + 1);
            else next = new Node(curr,, freq + 1);
            if (curr.keys.isEmpty()) {
            nodeMap.put(freq + 1, next);
        void removeNode(Node node) {
            if (node == head) {
                head =;
                if (head != null) head.prev = null;
            } else {
                if ( != null) {
           = node.prev;
        class Node {
            Node prev;
            Node next;
            int freq;
            LinkedHashSet<Integer> keys;
            Node(Node prev, Node next, int freq) {
                this.freq = freq;
                keys = new LinkedHashSet<>();
                this.prev = prev;
       = next;
                if (prev != null) {
           = 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);

Log in to reply

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