LRU Cache - codepath/compsci_guides GitHub Wiki
Problem Highlights
- π Leetcode Link: https://leetcode.com/problems/lru-cache/
- π‘ Problem Difficulty: Medium
- β° Time to complete: 10 to 13 mins
- π οΈ Topics: Linked Lists, Hash Table
- ποΈ Similar Questions: LFU Cache, Design In-Memory File System
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"]
[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4](/codepath/compsci_guides/wiki/2],-[1,-1],-[2,-2],-[1],-[3,-3],-[2],-[4,-4],-[1],-[3],-[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.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
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.
- Knowing the length of the list is important since we want to rotate only
- 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 _add_node(self, node):
"
Always add the new node right after head.
"
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
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
def _move_to_head(self, node):
"
Move certain node in between to the head.
"
self._remove_node(node)
self._add_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
self.head, self.tail = DLinkedNode(), DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
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;
self._move_to_head(node)
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 = DLinkedNode()
newNode.key = key
newNode.value = value
self.cache[key] = newNode
self._add_node(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
self._move_to_head(node)
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
/**
* Always add the new node right after head.
*/
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node){
/**
* Remove an existing node from the linked list.
*/
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node){
/**
* Move certain node in between to the head.
*/
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
/**
* Pop the current tail.
*/
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
// head.prev = null;
tail = new DLinkedNode();
// tail.next = null;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
// move the accessed node to the head;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
// pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}
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.