LRUCache: Case difference between OJ and local complier


  • 0
    W

    My code can not pass the OJ for the following test case:
    Input: 1,[set(2,1),get(2),set(3,2),get(2),get(3)]
    Output: [1,1,2]
    Expected: [1,-1,2]

    However, my code works correctly on the local machine. Any thought on the reason is appreciated.

    import java.util.HashMap;
    public class LRUCache {
        private static DLLNode head;
        private static DLLNode tail;
        private static int capacity;
        private static int length;
        private static HashMap<Integer,DLLNode> map = new HashMap<Integer,DLLNode>();
        
        public LRUCache(int capacity) {
            this.head = new DLLNode();
            this.tail = new DLLNode();
            this.head.next = tail;
            this.tail.pre = head;
            this.capacity = capacity;
            this.length = 0;
        }
        
        public static int get(int key) {
        	int result = -1;
            if(map.containsKey(key)) {
            	DLLNode tmp_node = map.get(key);
            	removeNode(tmp_node);
            	addLatestNode(tmp_node);
            	result = tmp_node.val;
            }
            return result;
        }
        
        public static void set(int key, int value) {
            if(map.containsKey(key)) {
                DLLNode tmp_node = map.get(key);
                tmp_node.val = value;
                removeNode(tmp_node);
                addLatestNode(tmp_node);
            } else {
                DLLNode new_node = new DLLNode(key,value);
                if(length<capacity) {
                    addLatestNode(new_node);
                    map.put(key,new_node);
                    length++;
                } else {
                    map.remove(tail.pre.key);
                    removeNode(tail.pre);
                    addLatestNode(new_node);
                    map.put(key,new_node);
                }
            }
        }
        
        private static void removeNode(DLLNode node) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
        
        private static void addLatestNode(DLLNode node) {
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
            node.pre = head;
        }
    }
    
    class DLLNode {
    	public int val;
    	public int key;
    	public DLLNode pre;
    	public DLLNode next;
    	public DLLNode(int key, int val) {
    		this.val = val;
    		this.key = key;
    	}
    	public DLLNode(){}
    }

  • 2
    A

    I suggest trying to use Java's LinkedList instead of your own. If it works, then test your DLL separately with all the use cases of the LRU cache. If both things work separately, they should work together now.

    Eclipse IDE and NetBeans provide nice features for debugging and checking the state of your list & map after each operation.

    Good luck!


  • 0
    W

    Thank you very much.

    I removed all the 'static' modifier in my code and it got accepted. I haven't figured out the reason yet, but thank you for your help!


  • 0
    A

    That makes a lot of sense. The "client" of the OJ that creates instances of your class for testing may be creating many at a time to test all cases in parallel. If everything is static, then only one instance can be run at a time, which was the reason it was working on your local machine. Congrats for the AC!


  • 0
    W

    Thank you for your comments. The parallel testing makes a lot of sense. I will try to avoid static variables.


Log in to reply
 

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