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?
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]]
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 4Match 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:
k % len(list) times. Note: This computation may not be necessary for some approaches.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
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);
}
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
