Basic Java LRU Cache implementation


  • 0
    A

    This way might have plenty of optimizations that can be made. However it is O(1) with get and O(n) (where n is equal to capacity) with put. This works in IDE but seems to encounter a bug on leetcode.

    import java.util.HashMap;
    import java.util.Map;
    
    class LRUCache {
        HashMap<Integer, Integer> cache = new HashMap<>();
        HashMap<Integer, Long> times = new HashMap<>();
        int capacity = 0;
        int maxCapacity = 0;
    
        public LRUCache(int capacity) {
            this.maxCapacity = capacity;
        }
    
        public int get(int key) {
            if (cache.keySet().contains(key)) {
                times.put(key, System.currentTimeMillis());
                return cache.get(key);
            }
            return -1;
        }
    
        public void put(int key, int value) {
            int placement  = key;
            if (capacity + 1 > maxCapacity) {
                long time = Long.MAX_VALUE;
                int position = 0;
                for (Map.Entry<Integer, Long> entry : times.entrySet()) {
                    if (entry.getValue() < time) {
                        time = entry.getValue();
                        position = entry.getKey();
                    }
                }
                cache.remove(position);
                times.remove(position);
            } else {
                capacity++;
            }
            cache.put(placement, value);
            times.put(key, System.currentTimeMillis());
        }
    
        public static void main(String[] args) {
            LRUCache cache = new LRUCache(2);
            cache.put(1,1);
            cache.put(2,2);
            int a = cache.get(1);
            cache.put(3,3);
            int b = cache.get(2);
            cache.put(4,4);
            int c = cache.get(1);
            int d = cache.get(3);
            int e = cache.get(4);
        }
    }
    

  • 0
    V

    Using a LinkedHashMap here is my favourite solution (quite well known, and used it in a previous interview).

    Not sure if this is sometimes considered a shortcut by some interviewers, anyway here's the code.

    Matter of taste on inheritance vs composition here.

    Complexity is O(1) for both get and put.

    import java.util.LinkedHashMap;
    import java.util.Map;
    
    public LRUCache<K, V> extends LinkedHashMap<K, V> {
      private int cacheSize;
    
      public LRUCache(int cacheSize) {
        super(10, 0.75, true);
        this.cacheSize = cacheSize;
      }
    
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() >= cacheSize;
      }
    }
    

Log in to reply
 

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