Saturday, 1 June 2019

LRU Cache - Implement using Java LinkedHashMap

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up
Could you do both operations in O(1) time complexity?

Example
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

LinkedHashMap was designed to be used as a Cache with customizable policies.
If you will read the documentation you will find a protected method removeEldestEntry where you can specify condition by which eldest entry will be removed.

package com.leetcode.caching;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache extends LinkedHashMap {

     private final int capacity;

     public LRUCache(int capacity) {
          this.capacity = capacity;
     }

     /**
      * Remove the key and add it again to map to make it most recently used.
      *
      * @param key
      * @return value
      */
     public int get(int key) {
          Integer removed = remove(key);
          if (removed == null) {
               removed = -1;
          } else {
               super.put(key, removed);
          }
          return removed;
     }

     /**
      * Remove if key already exists. Add the key on the top.
      *
      * @param key
      * @param value
      */
     public void put(int key, int value) {
          super.remove(key);
          super.put(key, value);
     }

     /**
      * If capacity is reached, remove the least used element from the map.
      * Check the intenal implememtation of the map.
      * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
      */
     @Override
     protected boolean removeEldestEntry(Map.Entry eldest) {
          return size() > capacity;
     }

     public static void main(String[] args) {
          LRUCache cache = new LRUCache(2);

          cache.put(1, 1);
          cache.put(2, 2);
          System.out.println(cache.get(1)); // returns 1
          cache.put(3, 3); // evicts key 2
          System.out.println(cache.get(2)); // returns -1 (not found)
          cache.put(4, 4); // evicts key 1
          System.out.println(cache.get(1)); // returns -1 (not found)
          System.out.println(cache.get(3)); // returns 3
          System.out.println(cache.get(4)); // returns 4

     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...