Amazon interview question
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.
Interview Answers
:v Just a hasmap along with a queue to store the keys should be good, no? Can we not use a hashmap?
public class LRUCache {
static class DoubleLinkedNode{
int val;
int key;
DoubleLinkedNode prev;
DoubleLinkedNode next;
public DoubleLinkedNode(int key,int val){
this.key=key;
this.val=val;
}
}
static class DoubleLinkedList{
DoubleLinkedNode head;
DoubleLinkedNode tail;
int capacity;
int len;
public DoubleLinkedList(int capacity){
this.capacity=capacity;
}
//precondition N0 exist
public void removeNode(DoubleLinkedNode N0){
//head/tail changes
if (len==1){
head=null; tail=null;
}
else {
if (N0==head) head=head.next;
if (N0==tail) tail=tail.prev;
}
//connection changes
if (N0.prev==null && N0.next!=null){N0.next.prev=null; N0.next=null;}
else if (N0.prev!=null && N0.next==null){N0.prev.next=null; N0.prev=null;}
else if (N0.prev!=null && N0.next!=null){N0.prev.next=N0.next; N0.next.prev=N0.prev; N0.prev=null; N0.next=null;}
//length changes
this.len--;
}
public void addNode(DoubleLinkedNode N0){
if (this.len==0) {this.head=N0; this.tail=N0;this.len++;}
else {
this.tail.next=N0;
N0.prev=this.tail;
this.tail=N0;
this.len++;
}
}
}
HashMap H;
DoubleLinkedList L;
public LRUCache(int capacity) {
this.H=new HashMap();
this.L=new DoubleLinkedList(capacity);
}
public int get(int key) {
if (H.keySet().contains(key)){
DoubleLinkedNode N=H.get(key);
this.set(key,N.val);
return N.val;
}
return -1;
}
public void set(int key, int value) {
//if key already exists
if (H.keySet().contains(key)){
L.removeNode(H.get(key));
DoubleLinkedNode N1=new DoubleLinkedNode(key,value);
H.put(key,N1);
L.addNode(N1);
}
//if key not yet exist
else {
DoubleLinkedNode N1=new DoubleLinkedNode(key,value);
H.put(key,N1);
L.addNode(N1);
if (L.len>L.capacity) {
DoubleLinkedNode oldHead=L.head;
L.removeNode(oldHead);
H.remove(oldHead.key);
}
}
}