Why the code from CC150 6th can not pass?


  • 0
    M

    The code below I copied from Cracking the code interview and it can not pass somehow(Checked a lot times without diff comparing to the code in book). I am hoping some one can help me figure out whats wrong with this code since I think all methods make sense to me. Thank you!

    private int maxCacheSize;
    private HashMap<Integer, LinkedListNode> map = new HashMap<Integer, LinkedListNode>();
    private LinkedListNode listHead = null;
    public LinkedListNode listTail = null;
    
    public LRUCache(int capacity) {
        maxCacheSize = capacity;
    }
    
    public int get(int key) {
        LinkedListNode item = map.get(key);
        if (item == null) return -1;
        
        if (item != listHead) {
            removeFromLinkedList(item);
            insertAtFrontOfLinkedList(item);
        }
        
        return item.value;
    }
    
    private void removeFromLinkedList(LinkedListNode node) {
        if (node == null) return;
        
        if (node.prev != null) node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;
        if (node == listTail) listTail = node.prev;
        if (node == listHead) listHead = node.next;
    }
    
    private void insertAtFrontOfLinkedList(LinkedListNode node) {
        if (listHead == null) {
            listHead = node;
            listTail = node;
        } else {
            listHead.prev = node;
            node.next = listHead;
            listHead = node;
        }
    }
    
    public boolean removeKey(int key) {
        LinkedListNode node = map.get(key);
        removeFromLinkedList(node);
        map.remove(key);
        return true;
    }
    
    
    
    public void set(int key, int value) {
        removeKey(key);
        
        if (map.size() >= maxCacheSize && listTail != null) {
            removeKey(listTail.key);
        }
        
        LinkedListNode node = new LinkedListNode(key, value);
        insertAtFrontOfLinkedList(node);
        map.put(key, node);
    }
    
    private static class LinkedListNode {
        private LinkedListNode next, prev;
        public int key, value;
        public LinkedListNode(int k, int v) {
            key = k;
            value = v;
        }
    }

Log in to reply
 

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