# LRU Cache

## 1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?
• What is an LRU?
• A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest amount of time. An LRU cache is built by combining two data structures: a doubly linked list and a hash map.You can read more here.
• What operations do we need to implement?
• You need to implement 1) Get the key / Check if the key exists 2) Put the key and 3) Delete the first added key

Run through a set of example cases:

``````Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[, [1, 1], [2, 2], , [3, 3], , [4, 4], , , ]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4``````

## 2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked Lists, the top three things we want to consider are:

• If we were able to take multiple passes of the linked list, would that help solve the problem?
• Knowing the length of the list is important since we want to rotate only `k % len(list)` times. Note: This computation may not be necessary for some approaches.
• Would using a dummy head as a starting point help simplify our code and handle edge cases?
• Since we are manipulating the order of the list, a dummy head may look like a good strategy, and it may work. However, we don’t necessarily need one to solve this problem.
• If we used two pointers to iterate through the list at different speeds, would that help us solve this problem?
• A slow and fast pointer may not help the problem.

## 3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Solve with a hashmap that keeps track of the keys and its values in the double linked list.

``````In get method we have to return -1 if key is not in our dict. If it does, then we have to move our key, value pair to the end of our dict. Now it is our most recent key, value pair.

In put method if key is not in our dict and we would go above capacity, then we remove first item in our dict by .popitem(last=False) method.

If we only update value of the existed key, then we have to pop the value from the dict and then assign the value, to put the key, value pair at the end of our dict (so we make the key, value pair most recent one).``````

⚠️ Common Mistakes

• If we have the iterator for a particular element then we can access that element in O(1) in any STL. That lets us find an element in our cache's linked list in O(1) time, instead of O(n).

## 4: I-mplement

Implement the code to solve the algorithm.

``````class DLinkedNode():
def __init__(self):
self.key = 0
self.value = 0
self.prev = None
self.next = None

class LRUCache():
"""
"""

def _remove_node(self, node):
"""
Remove an existing node from the linked list.
"""
prev = node.prev
new = node.next

prev.next = new
new.prev = prev

"""
Move certain node in between to the head.
"""
self._remove_node(node)

def _pop_tail(self):
"""
Pop the current tail.
"""
res = self.tail.prev
self._remove_node(res)
return res

def __init__(self, capacity):
"""
:type capacity: int
"""
self.cache = {}
self.size = 0
self.capacity = capacity

def get(self, key):
"""
:type key: int
:rtype: int
"""
node = self.cache.get(key, None)
if not node:
return -1

# move the accessed node to the head;

return node.value

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
node = self.cache.get(key)

if not node:
newNode.key = key
newNode.value = value

self.cache[key] = newNode

self.size += 1

if self.size > self.capacity:
# pop the tail
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
else:
# update the value.
node.value = value
``````public class LRUCache {

int key;
int value;
}

/**
*/

}

/**
* Remove an existing node from the linked list.
*/

prev.next = next;
next.prev = prev;
}

/**
* Move certain node in between to the head.
*/
removeNode(node);
}

/**
* Pop the current tail.
*/
removeNode(res);
return res;
}

private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;

public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;

// tail.next = null;

}

public int get(int key) {
if (node == null) return -1;

// move the accessed node to the head;

return node.value;
}

public void put(int key, int value) {

if(node == null) {
newNode.key = key;
newNode.value = value;

cache.put(key, newNode);

++size;

if(size > capacity) {
// pop the tail
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
}
}
}``````

## 5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

## 6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

• Time Complexity: O(1) both for put and get.
• Space Complexity: O(capacity) since the space is used only for a hashmap and double linked list with at most capacity + 1 elements. 