LRU Cache

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

 METHOD 1:

class LRUCache {

HashMap<Integer,Integer> map;

List<Integer> list;
int c;
public LRUCache(int capacity) 
{
    c=capacity;
    list=new ArrayList<>(capacity);
    map=new HashMap<>();
}

public int get(int key) 
{
    if(map.containsKey(key))
    {
        int temp=list.indexOf(key);
        list.remove(temp);
        list.add(key);
        return map.get(key);
    }
    return -1;
}

public void put(int key, int value)
{

    if(list.contains(key))
    {
        map.put(key,value);
        int temp=list.indexOf(key);
        list.remove(temp);
        list.add(key);
    }
    else
    {
    if(list.size()==c)
    {
        int temp=list.get(0);
        map.remove(temp);
        list.remove(0);
    }
    list.add(key);
    map.put(key,value);
    }
}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */ 

Here we are using map and list. Map stores key and value.
List is used to store key alone. It is also used to find the LRU keys.

1)get(key)
   a) In this method we are returning value of keys if it is present or else return -1.

   b)Once we are using that key, we have to update list to find used keys. To do this we are removing the key and updating the same key in list. By doing this recently used key adds at the end of the list and least used key reaches beginning of array.


2) put(key, value)
      a)If the key is already present then update the value and update the list similar to step (b) of get() method which is described above.

      b)If list reaches the capacity, then removes the LRU from list(which is at index 0) and using that element removes the particular key, value pair from map too. And after that update the list and map using given key, value.

     c)If it fails in any of those conditions, then just add key, value in map and update the list with the key.

Try it on Leetcode

METHOD 2:

 class LRUCache {

LinkedHashMap<Integer,Integer> map;

int c;
public LRUCache(int capacity)
{
    c=capacity;
    map=new LinkedHashMap<>(capacity);
}

public int get(int key)
{
    if(map.containsKey(key))
    {
        int value = map.get(key);
       map.remove(key);
        map.put(key, value);
        return map.get(key);
    }
  
    return -1;
}

public void put(int key, int value)
{

    if(map.containsKey(key))
    {
       map.remove(key);
        map.put(key, value);
    }
    else
    {
    if(map.size()==c)
    {
       List<Integer> listKeys = new ArrayList<Integer>(map.keySet());
        int removeKey = listKeys.get(0);
        map.remove(removeKey);
    }
    map.put(key,value);
    }
}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */


Here, is another optimized solution. We are going to use LinkedHashMap. The concept is similar to the above method. But for removing LRU element from map, we need create an updated arraylist using keyset and removing the first element. Remaining all concept are exactly similar to the above method. 

Try it on Leetcode


 

Reuslt Comparison - Here 83ms is Method 2 and 255ms is method 1

Please let us know your views in comment section.