Debugging this problem taught me a lesson on not to oversimplify


  • 0
    C

    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;
        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 = itr.next();
                kvStore.remove(lfuKey);
                freqMap.remove(lfuKey);
                head.keys.remove(lfuKey);
                if (head.keys.isEmpty()) {
                    removeNode(head);
                }
            }
            
            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;
                curr.keys.add(key);
                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);
            }
            next.keys.add(key);
            nodeMap.put(freq + 1, next);
        }
        
        void removeNode(Node node) {
            if (node == head) {
                head = head.next;
                if (head != null) head.prev = null;
            } 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;
            LinkedHashSet<Integer> keys;
            
            Node(Node prev, Node next, int freq) {
                this.freq = freq;
                keys = new LinkedHashSet<>();
                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);
     */
    

Log in to reply
 

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