My O(1) java implementation


  • 0
    Y

    The goal is to keep track of the order of update time and constant time searching, insertion and deletion.
    Using queue, we can track history and do constant time push to the end and poll from the head.
    Using hashtable, we can do constant time searching and deletion.
    The only problem is that we can't delete a key in the queue in constant time.
    My solution is to use an extra hashtable (or merged to the previous data hashtable) to store the parent node of all the keys in the queue, so that I can do constant time deletion in the queue.

    public class LRUCache {
    
        private final int capacity;
        private final ListNode head = new ListNode(-1);
        private final Map<Integer, ListNode> parents = new HashMap<Integer, ListNode>();
        private final Map<Integer, Integer> data = new HashMap<Integer, Integer>();
        
        private ListNode tail = head;
    
        public LRUCache(int capacity) { this.capacity = capacity; }
    
        public int get(int key) {
            if (data.containsKey(key)) {
                refereshKey(key);
                return data.get(key);
            } else { return -1; }
        }
    
        public void set(int key, int value) {
            if (data.containsKey(key)) { refereshKey(key); } 
            else { pushKey(key); }
            
            data.put(key, value);
            
            if (data.size() > capacity) { 
                // remove oldest key and data
                data.remove(removeKey(head).val); 
            }
        }
        
        /**
         * O(1)
         * move a key to the end of the queue
         */
        private void refereshKey(int key) { pushKey(removeKey(parents.get(key))); }
        
        /**
         * O(1)
         * push a key node to the end of the queue
         * @param node the node to be pushed
         */
        private void pushKey(ListNode node) {
            parents.put(node.val, tail);
            tail.next = node;
            tail = tail.next;
        }
        private void pushKey(int key) { pushKey(new ListNode(key)); }
    
        /**
         * O(1)
         * pull a node out from the queue.
         * @param parent the parent of the target node
         * @return the removed node
         */
        private ListNode removeKey(ListNode parent) {
            ListNode node = parent.next;
    
            if (node == tail) { tail = parent; } 
            else { parents.put(node.next.val, parent); } 
            parents.remove(node.val);
    
            parent.next = node.next;
            node.next = null;
    
            return node;
        }        
    }

Log in to reply
 

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