Probably the "best" Java solution - extend LinkedHashMap


  • 33
    M

    I didn't check all 9 pages that are in this forum already, so it's likely someone already posted a solution like this. The easiest solution and maybe most elegant is to just use the LinkedHashMap with the access-order flag set to true. The official documentation on it even mentions LRU caches and offers a method to overwrite specifically for a purpose like this.

    import java.util.LinkedHashMap;
    
    public class LRUCache {
        
        private Map<Integer, Integer> map;
        
        public LRUCache(int capacity) {
            map = new LinkedCappedHashMap<>(capacity);
        }
        
        public int get(int key) {
            if(!map.containsKey(key)) { return -1; }
            return map.get(key);
        }
        
        public void set(int key, int value) {
            map.put(key,value);
        }
    
        private static class LinkedCappedHashMap<K,V> extends LinkedHashMap<K,V> {
            
            int maximumCapacity;
            
            LinkedCappedHashMap(int maximumCapacity) {
                super(16, 0.75f, true);
                this.maximumCapacity = maximumCapacity;
            }
            
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > maximumCapacity;
            }
        }
    }

  • 0
    This post is deleted!

  • 0
    M

    Fair enough - thx ^^


  • 0
    This post is deleted!

  • 35

    Nice solution, but can be shortened:

    import java.util.LinkedHashMap;
    
    public class LRUCache {
    
        private Map<Integer, Integer> map;
    
        public LRUCache(int capacity) {
            map = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > capacity;
                }
            };
        }
    
        public int get(int key) {
            return map.getOrDefault(key, -1);
        }
    
        public void set(int key, int value) {
            map.put(key,value);
        }
    }

  • 0
    M

    Neat and good idea.


  • 1

    Meh, boring optimization, nothing compared to your idea/work. I didn't even know LinkedHashMap before you pointed it out :-) (then again, I'm not a Java guy)


  • 0
    L

    This is the shortest LRU Cache solution. Amazing Java's LinkedHashMap with Jealousy.


  • 0
    A

    its does not provide any help to use already existing data structure. thats the problem to implement this data structure on your own


  • 1

    @ajak6 Please define what exactly "on your own" means. And I think it does help to use already existing data structures. A lot, actually.


  • 0
    O

    Start to learn java recently, nice to know LinkedHashMap!! Glad to see Stefan again haha! (though I notice u start to write some java solutions couple of months ago


  • 0

    @StefanPochmann Probably he/she means that at the actual interview the interviewer expects you to code the data structure from scratch and not use some exotic external library that simplifies the problem.


  • 1

    @agave You'd say the Java standard library is "some exotic external library"?


  • 2

    @StefanPochmann: no, but the target of the interviewer is let you code, not testing your knowledge of the Java standard library. For example, in Python you can easily solve this problem by using collections.OrderedDict, but I don't think the interviewer will let you use it in a real interview. If I were an interviewer, I would just appreciate the fact that you know some useful libraries but that doesn't mean you're a good coder (probably you are, but it's not the point of the interview IMHO).


  • 0
    L
    This post is deleted!

  • 1
    L

    @agave I think it's fine to offer this solution to the interviewer. If he/she wants something else, then we could do it with less specialized library (HashMap, I mean, since nobody would expect a homegrown hash map for solving this problem).


  • 0
    P

    what's the python equivalent of LinkedHashMap?


  • 0
    S

    Nice solution! But they don`t allow to use linkedHashMap in interviews.


  • 0
    A

    @StefanPochmann If I am asked to sort an array in an interview , i don't think I am expected to use Collections.sort() or Arrays.sort() but rather to implement the algorithm. Thats what "on your own" means to me. Its good to know the library and can be clarified with the interviewer what does he/she expects.


  • -2
    R

    This solution is incorrect. It doesn't move the last accessed entry to most recently used position. This solution is more like FIFO(not LRU).


Log in to reply
 

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