My Java Solutions using HashMaps and Doubly Linked Lists


  • 0
    S
    import java.util.Hashtable;
    public class LFUCache {
    
        public class Node {
            Node next;
            Node prev;
            int key;
            public Node(int key) {
                this.next = null;
                this.prev = null;
                this.key = key;
            }
        }
        public class Bucket {
            /*
            this class essentailly is a container where everything inside has a certain frequency
            every bucket has a doubly linkedlist that is ordered according to frequency of use, so most frequent to least frequent
            */
            int freq;
            Node head;
            Node tail;
            Hashtable<Integer, Node> nodeMap; //maping the key to the node to which it belongs
            Bucket next;
            Bucket prev;
            public Bucket(int freq) {
                this.freq = freq;
                this.head = new Node(0);
                this.tail = new Node(0);
                this.head.next = this.tail;
                this.tail.prev = this.head;
                this.nodeMap = new Hashtable<>();
                this.next = null;
                this.prev = null;
            }
            
            public int removeTail() { //remove the least frequent value in the doubly linked list
    //        	System.out.println("HERE HERE " +  tail.prev.key);
                if(tail.prev==head)
                    return -1;
                Node removed = tail.prev;
                removed.prev.next = tail;
                tail.prev = removed.prev;
                int key = removed.key;
                nodeMap.remove(key);
                return key;
            }
            public void addToHead(int key) {
                Node added = new Node(key);
                added.next = head.next;
                added.prev = head;
                head.next.prev = added;
                head.next = added;
                
                nodeMap.put(key, added);
            }
            public void removeNode(int key) {
                Node current = nodeMap.get(key);
                current.prev.next = current.next;
                current.next.prev = current.prev;
                nodeMap.remove(key);
            }
    
        }
        
        Bucket bucketHead;
        Bucket bucketTail;
        Hashtable<Integer, Bucket> bucketMap; //maps frequency to bucket
        Hashtable<Integer, Integer> cache; //key value pairs of cache
        Hashtable<Integer, Integer> frequencyMap; //maps key to its frequency
        int capacity;
        
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
            bucketMap = new Hashtable<>();
            cache = new Hashtable<>();
            bucketHead = new Bucket(Integer.MAX_VALUE);
            bucketTail = new Bucket(Integer.MIN_VALUE);
            bucketHead.next = bucketTail;
            bucketTail.prev = bucketHead;
            frequencyMap = new Hashtable<>();
        }
        public void updateFrequency(int key) {
            int freq = frequencyMap.get(key); //returns frequency associated with key
            Bucket current = bucketMap.get(freq); //returns bucket associated with frequency
            Bucket next = bucketMap.get(freq+1);
            if(next==null) {
                //create bucket and insert it into its right position and insert the node in it
                next = new Bucket(freq+1);
                next.prev = current.prev; //insert bucket in the bucket linked list
                next.next = current;
                current.prev = next;
                bucketMap.put(freq+1, next);
            }
            next.addToHead(key); //insert key into top of bucket linked list
            //update frequency of key and remove from previous bucket
            current.removeNode(key);
            if(current.head.next==current.tail) {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                bucketMap.remove(freq);
            }
            frequencyMap.put(key, freq+1);
        }
        
        public int get(int key) {
            if(cache.containsKey(key)) {
                //update freq and move to top of LRU cache
                updateFrequency(key);
                return cache.get(key);
            }
            return -1;
        }
        
        public void put(int key, int value) {
            if(capacity==0)
                return;
            if(cache.containsKey(key)) {
                //update its frequency
                updateFrequency(key);
                cache.put(key, value);
                return;
            }
            if(cache.size()+1 > capacity) {
                //remove from the tail bucket the node at the tail
                Bucket current = bucketTail.prev; //get least frequent bucket
                int k = current.removeTail(); //remove its least frequent node
                int freq = frequencyMap.get(k);
                cache.remove(k);
                frequencyMap.remove(k);
                //if bucket is empty remove bucket
                if(current.head.next==current.tail) {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    bucketMap.remove(freq);
                }
            }
            //add new key, it frequency will be 1 and it will be added to the begining of the bucket
            Bucket current = bucketMap.get(1);
            if(current==null) {
                //create new bucket, add it previous to the tail and add to it
                current = new Bucket(1);
                current.next = bucketTail;
                current.prev = bucketTail.prev;
                bucketTail.prev.next = current;
                bucketTail.prev = current;
                bucketMap.put(1, current);
            }
            current.addToHead(key);
            frequencyMap.put(key, 1);
            cache.put(key, value);
        }
    }
    
    /**
     * 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.