Failing testcase 16


  • 1
    P

    Hi,

    Can someone tell me what might be wrong with this LRU code? I thought everything looked okay but I'm only passing 15/18 test cases. Any help would be greatly appreciated, I'm going nuts, thanks!

    public class LRUCache {
        
        private class Node {
            private int key;
            private int val;
            private Node next;
            private Node prev;
            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
        
        private Map<Integer, Node> map;
        private int capacity;
        private Node head;
        private Node tail;
    
        public LRUCache(int capacity) {
            map = new HashMap<>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            removeNode(node);
            addToFront(node);
            return node.val;
        }
        
        private void removeNode(Node node) {
            if (head == node) {
                head = node.next;
            }
            if (tail == node) {
                tail = node.prev;
            }
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
        }
        
        private void addToFront(Node n) {
            if (head == null) {
                head = n;
                tail = n;
                return;
            }
            n.next = head;
            head.prev = n;
            head = n;
        }
        
        public void put(int key, int value) {
            Node n = map.get(key);
            if (n == null) {
                n = new Node(key, value);
                map.put(key, n);
            } else {
                removeNode(n);
                n.val = value;
            }
            addToFront(n);
            if (map.size() > capacity) {
                map.remove(tail.key);
                removeNode(tail);
            }
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(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.