Java O(1) solution with explainations (HashMap + 2 custom types of double-linked lists)


  • 0
    B

    Hi,

    At the moment, the explainations are written as comments in the code. I'll probably move them as text when I have some time. Feel free to leave a comment.

    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * A cache used to store and retrieve key/value pairs using the
     * Least Frequently Used policy for choosing which key to remove
     * when the cache is full.
     * <p>
     * The cache has a fixed size. When a new key needs to be stored
     * and the cache is full, the Least Frequently Used is discarded.
     * If several keys have the same frequency, the Least Recently
     * Used is discarded.
     * </p><p>
     * This implementation uses a HashMap and two kinds of
     * doubly-linked lists. This allows all operations run in O(1)
     * (see each operation comment for detailled explanations).
     * </p><p>
     * So, the LFUCache consists of a HashMap which associates each
     * key with a unique QueueNode and of a doubly-linked list of
     * FrequencyNodes.
     * </p><p>
     * Each FrequencyNode contains its frequency, a pointer to the
     * previous and next FrequencyNodes in the list and two pointers
     * (head and tail) to a doubly-linked list of QueueNodes which
     * contains all the QueueNodes associated with keys of the same
     * frequency as the FrequencyNode.
     * </p><p>
     * Each QueueNode stores its key/value pair, pointers to the
     * previous and next QueueNodes in the list of QueueNodes of
     * same frequency and a pointer to the FrequencyNode which
     * contains this list.
     * </p><p>
     * Finally, I used sentinel nodes in order to simplify the code.
     * With sentinel nodes, you can safely link/unlink in the list
     * without ever needing to check for null pointers.
     * </p><p>
     * <b>Class Invariants:</b>
     * </p><p>
     * - There's only one QueueNode per key in the cache. This is
     * ensured because QueueNodes are created only when a new key
     * is added.
     * </p><p>
     * - FrequencyNodes are linked in increasing order of frequency.
     * This is true because we always add FrequencyNodes by increment
     * of frequency by one, one at a time and only if needed.
     * Similarly, FrequencyNodes are removed one at a time, without
     * changing the order of the list.
     * </p><p>
     * - For any FrequencyNode (except the sentinel), the list of
     * QueueNodes has at least one element. We ensure that by
     * checking and removing empty FrequencyNodes after each
     * frequency update.
     * </p><p>
     * - Each list of QueueNodes is sorted from Least Recently
     * Used (head.next) to Most Recently Used (tail). That is true
     * because nodes are always added at the tail. And when we
     * remove some, the order doesn't change.
     * </p>
     */
    public class LFUCache {
        
        /**
         * A node to store all the QueueNodes with the same frequency.
         * <p>
         * The list of QueueNodes contains at least one element unless
         * this Frequency node is a sentinel. QueueNodes are always
         * added at the end of the list to ensure that they are sorted
         * from Least Recently Used (head) to Most Recently Used (tail).
         */
        private static class FrequencyNode {
            
            /**
             * This node's frequency
             */
            final int freq;
            
            /**
             * Link to the previous node in the list (with lower frequency)
             */
            FrequencyNode prev;
            
            /**
             * Link to the next node in the list (with higher frequency)
             */
            FrequencyNode next;
            
            /**
             * Link to the head of the list of QueueNodes with the same
             * frequency (head is the Least Recently used)
             */
            QueueNode head;
            
            /**
             * Link to the tail of the list of QueueNodes with the same
             * frequency (tail is the Most Recently used)
             */
            QueueNode tail;
            
            /**
             * Constructs a sentinel FrequencyNode with an enmpty list
             * of QueueNodes.
             */
            public FrequencyNode(int freq) {
                this.freq = freq;
                // Sentinel nodes to simplify the code
                this.head = new QueueNode();
                this.tail = new QueueNode();
                this.head.next = tail;
                this.tail.prev = head;
            }
            
            /**
             * Constructs a FrequencyNode and adds it between prev and next.
             * Requires that prev.freq + 1 = this.freq < next.freq.
             */
            public FrequencyNode(int freq, FrequencyNode prev, FrequencyNode next) {
                this(freq);
                this.prev = prev;
                this.next = next;
                prev.next = this;
                next.prev = this;
            }
            
            /**
             * Removes the given node from the list of QueueNodes.
             * If the QueueNode list becomes empty, remove this
             * FrequencyNode from the cache (unless it's the head).
             * This is done easily by linking prev and next.
             * This operation takes O(1).
             * Requires that node.parent = this.
             */ 
            public void removeNode(QueueNode node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                if ((freq != 0) && (head.next == tail)) {
                    prev.next = next;
                    next.prev = prev;
                }
            }
            
            /**
             * Moves the specified node at tail of the FrequencyNode
             * with frequency this.freq + 1. If no FrequencyNode
             * exist with that frequency (we only need to check the
             * next one), one is created and inserted just after
             * the current one. The queueNode is then moved to the
             * FrequencyNode with the incremented frequency.
             * The current FrequencyNode is then removed if needed.
             * This operation takes O(1).
             * Requires that node.parent = this.
             * This has the side-effect that node will point to
             * the FrequencyNode with frequency = this.freq + 1.
             */
            public void incrementFreq(QueueNode node) {
                FrequencyNode nextNode = next;
                if (nextNode.freq != freq + 1) {
                    nextNode = new FrequencyNode(freq + 1, this, next);
                }
                removeNode(node);
                nextNode.addLast(node);
            }
            
            /**
             * Helper method to link a QueueNode at the tail of the list.
             * This operation takes O(1).
             * This has the side-effect that node will point to the
             * current node.
             */
            private void addLast(QueueNode node) {
                node.prev = tail.prev;
                node.next = tail;
                tail.prev.next = node;
                tail.prev = node;
                node.parent = this;
            }
        }
        
        /**
         * A mutable class used to construct a Deque.
         * The QueueNode stores the key and its associated value as well
         * as pointers to the previous and next nodes in the queue and
         * a pointer to the FrequencyNode holding the queue.
         */
        private static class QueueNode {
            
            /**
             * The key that this node belongs to
             */
            final int key;
             
            /**
             * The value associated to the key. This value can change via
             * the {@code put} method of the {@LFUCache} class.
             */
            int value;
            
            /**
             * The previous node in the queue
             */
            QueueNode prev;
            
            /**
             * The next node in the queue
             */
            QueueNode next;
            
            /**
             * The FrequencyNode holding this queue
             */
            FrequencyNode parent;
            
            /**
             * Constructs a sentine QueueNode.
             */
            public QueueNode() {
                this.key = Integer.MIN_VALUE;
                this.value = Integer.MIN_VALUE;
                this.parent = null;
            }
            
            /**
             * Constructs a QueueNode and adds it to the given FrequencyNode.
             */
            public QueueNode(int key, int value, FrequencyNode parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
                this.parent.addLast(this);
            }
            
            /**
             * Removes this QueueNode from its parent's queue.
             * This operation takes O(1).
             */
            public void removeFromQueue() {
                parent.removeNode(this);
            }
            
            /**
             * Moves this QueueNode to the FrequencyNode with a
             * frequency increased by one and removes its current
             * parent from the LFUCache if needed.
             * This operation takes O(1).
             */
            public void incrementFreq() {
                parent.incrementFreq(this);
            }
        }
        
        /**
         * A map to associate each key to a unique QueueNoode
         */
        private Map<Integer, QueueNode> infoByKey;
        
        /**
         * The sentinel node starting the list of FrequencyNodes.
         * It has a frequency of 0.
         */
        private FrequencyNode head;
        
        /**
         * The maximum number of unique keys that the cache can hold
         */
        private final int capacity;
    
        /**
         * Constructs an empty LFUCache with the given capacity.
         * 
         * @param capacity the maximum number of unique keys that the cache can hold
         */
        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.infoByKey = new HashMap<>();
            this.head = new FrequencyNode(0);
            // Sentinel node to simplify the implementation
            FrequencyNode sentinel = new FrequencyNode(Integer.MAX_VALUE);
            this.head.next = sentinel;
            sentinel.prev = this.head;
        }
        
        /**
         * Returns the value associated with the given key or -1
         * if the key is not in the cache. if the key is present,
         * its frequency is incremented.
         * This operation takes O(1).
         * 
         * @param key a key
         * @return  the value associated with the given key or -1
         * if the key is not in the cache
         */
        public int get(int key) {
            if (!infoByKey.containsKey(key)) {
                return -1;
            }
            QueueNode keyNode = infoByKey.get(key);
            keyNode.incrementFreq();
            return keyNode.value;
        }
        
        /**
         * Adds the key/value pair to the cache or just update the
         * value if the key is already present.
         * If the key is new and the cache is full, the Least
         * Frequently Used key/value pair is discarded first.
         * This operation takes O(1).
         * 
         * @param key a key. This must be a positive number
         * @param value the value to associate with the key
         */
        public void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
            QueueNode keyNode;
            if (infoByKey.containsKey(key)) {
                keyNode = infoByKey.get(key);
                keyNode.value = value;
            } else {
                if (infoByKey.size() == capacity) {
                    deleteLFULRUKey();
                }
                keyNode = new QueueNode(key, value, head);
                infoByKey.put(key, keyNode);
            }
            keyNode.incrementFreq();
        }
        
        /**
         * Removes the Least Frequently Used key from the cache. If there's more than
         * one key with the lowest frequency, the Least Recently Used is removed.
         * This operation takes O(1).
         */
        private void deleteLFULRUKey() {
            // The nodes with the LFU keys are in the FrequencyNode just after head.
            // This node queue has at least one element (class invariant) and the first
            // one is the least frequently used since we always add new elements at the
            // tail.
            QueueNode nodeToRemove = head.next.head.next;
            nodeToRemove.removeFromQueue();
            infoByKey.remove(nodeToRemove.key);
        }
        
    
    
    /**
     * 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);
     */    public static void main(String[] args) {
            LFUCache cache = new LFUCache(2);
            cache.put(1, 1);
            cache.put(2, 2);
            System.out.println(cache.get(1));
            cache.put(3, 3);
            System.out.println(cache.get(2));
            System.out.println(cache.get(3));
            cache.put(4, 4);
            System.out.println(cache.get(1));
            System.out.println(cache.get(3));
            System.out.println(cache.get(4));
        }
    }
    

Log in to reply
 

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