Title:

LRU Cache - Strategy 1

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.
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.put(4, 4); // evicts key 1
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:

1. Consider the cache as a variant of a FIFO linked list in which each node contains a key and a value.
The nodes in the linked list always are kept sorted based on the access time
(i.e; based on the time for get and put request of the keys)
Each node in the list has a unique key; i.e.; there are no two nodes with the same keys.
2. To keep the linked list sorted based on the access time, do the following:
1. Upon each put and get request for a key, first find the key in the linked list.
2. If the key exists in the linked list, move it to the end of the linked list, and perform put and get operations.
3. Else
1. If the request is put and the size of the list has not exceeded the capacity of the cache,
add a new node to the end of the list related to the new key value pair.
2. If the size of FIFO is exceeding the given capacity, evict the first node of the linked list.
3. If the requests is get, the request is not valid and return -1.
Note: In this design strategy, the time of put and get is proportional to the size of the linked list at each step and it is not highly time efficient.

Run-Time Analysis:

GitHub Project:

Code:

``` package LeastRecentlyUsedCache; /** * @author Mahsa Sadi * * @since 2020 - 05 - 19 * * License Creative Commons * * Copyright by Mahsa Sadi * * * */ import java.util.HashMap; import java.util.Map; public class LRUCacheS2 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 the cache as a variant of a FIFO linked list in which each node contains a key and a value. * The nodes in the linked list always are kept sorted based on the access time * (i.e; based on the time for get and put request of the keys). * Each node in the list has a unique key; i.e.; there are no two nodes with the same keys. * * * * * 2- To keep the linked list sorted based on the access time: * * 1- Upon each put and get request for a key, first find the key in the linked list. * * 2- If the key exists in the linked list, move it to the end of the linked list, and perform put and get operations. * * 3- Else * * 1- If the request is put and the size of the list has not exceeded the capacity of the cache, * add a new node to the end of the list related to the new key value pair. * * 2- If the size of FIFO is exceeding the given capacity, evict the first node of the linked list. * * 3- If the requests is get, the request is not valid and return -1. * * * * Note: The time of put and get is proportional to the size of the linked list at each step and it is not highly time efficient. * */ LinkedSet recentUsage; int counter; int capacity; LRUCacheS2 (int capacity) { recentUsage = new LinkedSet (); counter = 0; this.capacity = capacity; } public void put (int key, int val) { recentUsage.add(key, val, capacity); } public int get (int key) { int val = recentUsage.add(key); return val; } public class NodeList { int key; int val; NodeList next; NodeList (int key, int val) { this.key = key; this.val = val; next = null; } void setNext (NodeList next) { this.next = next; } } public class LinkedList { NodeList first; NodeList last; int length; LinkedList () { first = null; last = null; length = 0; } void add (int key, int val) { /* * Adds the value to the end of the list */ NodeList n = new NodeList (key, val); if (first == null) { first = n; last = n; } else { last.setNext(n); last = n; } length++; } public int deleteFirst () { int key = first.key; first = first.next; length--; return key; } NodeList find (int key) { /* * Returns the node previous to the node with the wanted value; */ NodeList n = null; NodeList currentNode = first; NodeList previousNode = first; boolean found = false; while (currentNode != null && ! found) { if (currentNode.key == key) { n = previousNode; found = true; } else { previousNode = currentNode; currentNode = currentNode.next; } } return n; } } public class LinkedSet extends LinkedList { public LinkedSet () { super (); } public int add (int key) { int value = -1; NodeList n = find (key); if ( n != null) { if (n.key == key) { value = n.val; } else { value = n.next.val; } moveToTheEndOfList (n, key, value); } return value; } public void add (int key, int val, int capacity) { /* * If the node with the wanted value does not exit in the list, it adds a new node with the wanted value to the end of the list; * Else if the node with the wanted value exist in the list, it will be moved to the end of the list; */ NodeList n; if (first == null) addToTheBeginningOfList (key, val); else { n = find (key); if (n == null) { if (length == capacity) deleteFirst(); if (length == 0) addToTheBeginningOfList (key, val); else addToTheEndOfList (key, val); } else moveToTheEndOfList (n, key, val); } } public void addToTheBeginningOfList (int key , int val) { NodeList n = new NodeList (key, val); first = n; last = n; length++; } public void addToTheEndOfList (int key , int val) { NodeList n = new NodeList (key, val); last.next = n; last = n; length++; } public void moveToTheEndOfList (NodeList n, int key, int val) { NodeList nodeToBeMoved; if (first != last && !(n.next.key == key && n.next == last)) { if (n.key == key) { /* * In case the node containing the wanted value is the first node; */ nodeToBeMoved = n; first = n.next; } else { nodeToBeMoved = n.next; n.next = nodeToBeMoved.next; } last.next = nodeToBeMoved; nodeToBeMoved.next = null; last = nodeToBeMoved; } last.val = val; } } } ```