Why my solution exceeds time limit


  • 0
    R

    I checked others' solutions who use node structure with tail and head pointer to make the program much faster... But, what's the problem in my code, which is basically based on HashMap. (suppose concurrency is not an issue here)

    import java.util.concurrent.ConcurrentHashMap;
    public class LRUCache {
        
        private HashMap<Integer,CacheItem> cacheMap;
        private int capacity;
        
        public LRUCache(int capacity) {
            cacheMap=new HashMap<Integer,CacheItem>(capacity);
            this.capacity=capacity;
        }
        
        public int get(int key) {
            if(checkExistence(key)){
                cacheMap.get(key).incrementWeight();
                return cacheMap.get(key).getValue();
            }else{
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if(checkExistence(key)){
                cacheMap.get(key).setValue(value);
                cacheMap.get(key).incrementWeight();
            }
            else{
                if(cacheMap.size()==this.capacity){
                    removeLRUItem();
                }
                CacheItem item=new CacheItem();
                item.setValue(value);
                this.cacheMap.put(key,item);
            }
        }
        
        private void removeLRUItem(){
            int weight=Integer.MAX_VALUE;
            int key=-1;
            for(int k:this.cacheMap.keySet()){
                CacheItem item=this.cacheMap.get(k);
                if(item.getWeight()<weight){
                    weight=item.getWeight();
                    key=k;
                }
            }
            this.cacheMap.remove(key);
        }
        
        private boolean checkExistence(int key){
            return cacheMap.keySet().contains(key);
        }
        
        class CacheItem{
            private int value;
            private int weight=0;
            
            public void setValue(int value){ this.value=value;}
            public int getValue(){return this.value;}
            
            public void incrementWeight(){++this.weight;}
            public int getWeight(){return this.weight;}
        }
    }

  • 0
    R

    Figure it out by myself... Because of using the structure of Nodes with tail and head, the LRU element always stays at the tail. It prevents a linear search over all elements to search for the LRU element...


Log in to reply
 

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