59 lines
1.7 KiB
Markdown
59 lines
1.7 KiB
Markdown
# Least Recently Used cache
|
|
|
|
> Design and build a LRU cache, which evicts the least recently used item. The cache should map from keys to values (allowing to insert and retrieve a value associated with a particular key), and be initialized with a max size. When it is full, it should evict the LRU item.
|
|
|
|
## First idea
|
|
|
|
Create linked list with max size, add in forward order. When a value is to be retrieved, visit the node and put it in the back. Keep a counter for number of items added, when it surpasses `max_len`, drop the head.
|
|
|
|
```java
|
|
class Node {
|
|
Node next = null;
|
|
int key;
|
|
int value;
|
|
int max_size;
|
|
|
|
public Node(int k, int v, int max_size){
|
|
this.key = k;
|
|
this.value = v;
|
|
this.max_size = max_size;
|
|
}
|
|
|
|
void appendToTail(int k, int v){
|
|
Node end = new Node(k, v);
|
|
Node head_tmp = this;
|
|
Node n = this;
|
|
|
|
int i = 0;
|
|
while (n.next != null){
|
|
// if max value is achieved, delete head node (the one accessed the last)
|
|
if(i >= head_tmp.max_size){
|
|
head_tmp = head_tmp.next;
|
|
i--;
|
|
}
|
|
n = n.next;
|
|
i++;
|
|
}
|
|
n.next = end;
|
|
}
|
|
|
|
int retrieve_value(int k){
|
|
while (n.next != null){
|
|
if(n.key == k){
|
|
return n.value;
|
|
}
|
|
n = n.next;
|
|
}
|
|
return -1
|
|
}
|
|
}
|
|
```
|
|
|
|
## Hints
|
|
|
|
Both a hash table and a doubly linked list would be useful, combine the two.
|
|
|
|
## Solution
|
|
|
|
A singly linked list is fast for eviction but slow for retrieval of keys. Make a doubly linked list, where it's easy to remove the middle element. The hash table maps to each linked list node rather than the value.
|