Title:
LRU Cache - Strategy 2
Link to LeetCode:
https://leetcode.com/problems/lru-cache/
Specification:
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?
Examples:
Example 1:
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
Initial Code and Signature:
public class LRUCache {
public LRUCache ()
{
}
public LRUCache(int capacity)
{
}
public int get(int key)
{
return 0;
}
public void put(int key, int value)
{
}
}
Algorithm:
This strategy is more time-efficient.Run-Time Analysis:
GitHub Project:
Code:
package LeastRecentlyUsedCache;
/**
* @author Mahsa Sadi
*
* @since 2020 - 05 - 21
*
* License Creative Commons
*
* Copyright by Mahsa Sadi
*
*
*/
import java.util.HashMap;
import java.util.Map;
import LinkedList.NodeList;
public class LRUCacheS4 extends LRUCache {
/**
* Problem: LRU Cache
*
*
*
*
* Description:
*
* 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?
*
*
* Algorithm:
*
* 1- Consider a Hash Table for (Key, Value) pairs.
* The size of the hash table is equal to the given capacity of the cache.
*
*
*
* 2- Consider a FIFO LinkedList that records the order of all get and put requests.
* Each node in the FIFO LinkedList contains a Key.
* With each new put or each new and valid get request a node containing the requested key is added to the end of FIFO.
*
*
*
* 3- Consider a Hash Table for (Key, #Access Times).
* With each put or valid get request for a key, increase the #access times related to the key by one.
*
*
*
* 4- Before putting a *new* (Key, Value) pair, check the current size of the cache hash table.
* If the size is equal to the given capacity, evict one (key, value) pair from the cache.
*
*
* 5- To evict a key, check the FIFO Linked List:
*
* 1- Delete the first node in the FIFO linked list, and get its key.
* 2- Check the #accessTimes of the key in the second hash table and decrease this number by one.
* 3- If #access time - 1 == 0, the key should be evicted from the cache hash table.
* 4- else go to 1- and continue until one key is evicted.
*
*
*
*/
LinkedList timeStamps;
Map <Integer, Integer> cache;
Map <Integer, Integer> accessTimes;
int capacity;
int length;
public LRUCacheS4 (int capacity)
{
timeStamps = new LinkedList ();
cache = new HashMap <Integer, Integer> ();
accessTimes = new HashMap <Integer, Integer> ();
this.capacity = capacity;
length = 0;
}
public void put(int key, int value)
{
if (this.length == this.capacity && ! cache.containsKey(key))
evictFromCache ();
addTimeStamp (key);
if (!cache.containsKey(key))
this.length++;
cache.put(key, value);
}
public int get (int key)
{
if (cache.containsKey(key))
{
addTimeStamp (key);
return cache.get(key);
}
else
return -1;
}
public void addTimeStamp (int key)
{
if (timeStamps.getFirst() != null && key == timeStamps.getFirst())
{
timeStamps.deleteFirst();
timeStamps.add(key);
}
else
{
timeStamps.add(key);
if (accessTimes.containsKey(key))
accessTimes.put(key, accessTimes.get(key) + 1 );
else
{
accessTimes.put(key, 1);
}
}
}
public void evictFromCache ()
{
boolean evicted = false;
int keyToBeRemoved;
int times;
while (! evicted)
{
keyToBeRemoved = timeStamps.deleteFirst();
times = accessTimes.get(keyToBeRemoved) - 1;
if (times == 0)
{
cache.remove(keyToBeRemoved);
accessTimes.remove (keyToBeRemoved);
evicted = true;
this.length --;
}
else
{
accessTimes.put (keyToBeRemoved, times);
}
}
}
public void printCache ()
{
String cache = "";
for (Integer key : this.cache.keySet() )
{
cache += "(" + key + "," + this.cache.get(key) + ") ";
}
System.out.println (cache + "\n");
}
public class NodeList {
int val;
NodeList next;
NodeList (int val)
{
this.val = val;
next = null;
}
void setNext (NodeList next)
{
this.next = next;
}
}
public class LinkedList {
NodeList first;
NodeList last;
int length;
public LinkedList ()
{
first = null;
last = null;
length = 0;
}
public int getLength ()
{
return this.length;
}
public Integer getFirst ()
{
Integer val = null;
if (this.first != null)
val = this.first.val;
return val;
}
public void add (int val)
{
/*
* Adds the value to the end of the list
*/
NodeList n = new NodeList (val);
if (first == null)
{
first = n;
last = n;
}
else
{
last.next = n;
last = n;
}
length++;
}
public int deleteFirst ()
{
int val = first.val;
if (length > 1 )
first = first.next;
else
{
first = null;
last = null;
}
length--;
return val;
}
}
}