O(1) solution, with hashmap + maintaining frequency buckets with double linked list


  • 0
    Z
    1. frequency buckets are maintained by double linked list
    2. frequency bucket maintains 1. count, 2. <key, value> node double linked list with same frequency, 3. <key, value> node also contains bucket reference.
    3. hash map stores key and <key, value> node reference

    it's not hard to get the idea, took some time to implement it and get it run

    public class LFUCache {
        private int CAPACITY;
        private final Map<Integer, LFUNode> map = new HashMap<>();
        private FrequencyNode freqHead, freqTail;
    
        public LFUCache(int capacity) {
            this.CAPACITY = capacity;
            freqHead = new FrequencyNode(0);
            freqTail = new FrequencyNode(-1);
            freqHead.next = freqTail;
            freqHead.prev = freqHead;
        }
    
        public int get(int key) {
            if (CAPACITY == 0 || !map.containsKey(key)) {
                return -1;
            }
    
            LFUNode node = map.get(key);
            updateNode(node);
    
            return node.value;
        }
    
        public void set(int key, int value) {
            if (CAPACITY == 0) {
                return;
            }
    
            if (map.containsKey(key)) {
                LFUNode node = map.get(key);
                node.value = value;
                updateNode(node);
            } else {
                LFUNode node = new LFUNode(key, value);
                if(map.size() == CAPACITY) {
                    LFUNode toBeRemoved = freqHead.next.head.next;
                    removeNode(toBeRemoved);
                    map.remove(toBeRemoved.key);
                }
                updateNodeFromFreqNode(freqHead, node);
                map.put(key, node);
            }
        }
    
        private void removeNode(LFUNode node) {
            FrequencyNode freqNode = node.freqNode;
            removeLFUNode(node);
            if(freqNode.count == 0) {
                removeFreqNode(freqNode);
            }
        }
    
        private void updateNode(LFUNode node) {
            FrequencyNode freqNode = node.freqNode;
            removeLFUNode(node);
            updateNodeFromFreqNode(freqNode, node);
            if(freqNode.count == 0) {
                removeFreqNode(freqNode);
            }
        }
    
        private void updateNodeFromFreqNode(FrequencyNode freqNode, LFUNode node) {
            int freq = freqNode.frequency;
            if (freqNode.next.frequency != freq + 1) {
                FrequencyNode newFreq = new FrequencyNode(freq + 1);
                insertFreqNodeAfter(freqNode, newFreq);
                insertLFUNode(newFreq, node);
            } else {
                insertLFUNode(freqNode.next, node);
            }
        }
    
        private void insertFreqNodeAfter(FrequencyNode cur, FrequencyNode freqNode) {
            freqNode.next = cur.next;
            cur.next = freqNode;
            freqNode.prev = cur;
            freqNode.next.prev = freqNode;
        }
    
        private void removeFreqNode(FrequencyNode freqNode) {
            freqNode.prev.next = freqNode.next;
            freqNode.next.prev = freqNode.prev;
            freqNode.next = freqNode.prev = null;
        }
    
        private void removeLFUNode(LFUNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.freqNode.count--;
            node.freqNode = null;
            node.next = node.prev = null;
        }
    
        private void insertLFUNode(FrequencyNode freqNode, LFUNode node) {
            freqNode.count++;
            node.freqNode = freqNode;
            LFUNode tail = freqNode.tail;
            tail.prev.next = node;
            node.prev = tail.prev;
            node.next = tail;
            tail.prev = node;
        }
    
        class LFUNode {
            LFUNode prev, next;
            int key;
            int value;
            FrequencyNode freqNode;
            LFUNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    
        class FrequencyNode {
            FrequencyNode prev, next;
            int frequency;
            int count;
            LFUNode head, tail;
            FrequencyNode(int frequency) {
                this.frequency = frequency;
                head = new LFUNode(-1, -1);
                tail = new LFUNode(-1, -1);
                head.next = tail;
                tail.prev = head;
            }
        }
    }
    

Log in to reply
 

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