Java LinkedHashMap 17 ms beats 82%


  • 0
    S
     import java.util.LinkedHashMap;
        
        
        /**
        * both put AND get methods count as an access or 'use'
        * 
        * 
        * */
        
        class LRUMap<K, V> extends LinkedHashMap<K, V> {
            private int cacheSize ; 
            
            public LRUMap(int capacity) {
                super(capacity, 0.75f, true) ; //access-based eviction set to 'true' (as opposed to 'insertion'-based eviciton) 
                cacheSize = capacity ;
            }
            
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > cacheSize ; 
            }
        }
        
        
        public class LRUCache  {
            
            LRUMap<Integer, Integer> map ; //use extension of LinkedHashMap here
          
            
            public LRUCache(int capacity) {
                map = new LRUMap<Integer, Integer>(capacity) ; //make sure to pass 'capacity' on to LinkedHashMap ctor
            }
            
          
            public int get(int key) {
                
                if(map.containsKey(key)) {
                    return map.get(key) ; 
                    
                }
                return -1; 
            }
            
            public void set(int key, int value) {
             
              
                map.put(key, value) ; //removeEldestEntry takes care of removing the 'oldest' entry 
              
            }
        
        }

  • 1
    J

    Just curious, are solutions like this supposed to be allowed? I feel like the whole point of this question was to implement some variation of the linked hashmap, otherwise this question wouldn't be marked with such high difficulty rating.


  • 0
    H

    There were a lot of questions I wanted to ask when I read the question. Can I use LinkedHashMap? Can I even use HashMap? Can I use any java collections at all? Using HashMap and storing nodes with links is easier than also having to implement a tree or hashmap or something like that.


Log in to reply
 

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