Adobe Interview Question
Computer ScientistsTeam: PSE
Country: India
Interview Type: In-Person
Use doubly linked list with a hash fucntion.
Hash funtion helps locate a node.
Double LL is needed when a node is accessed and need to be moved to head of LL(recently used.)
when elements in LL > threshold. remove element at end of LL.
your soln is better. Many ppl suggested on ur lines but the thing you pointed is most recent used will be placed on the head of the list and least recent used on tail of the list. Most of the time you need to work with modification of head of the list only when you dont find your match then you need to traverse down the tail
import java.util.HashMap;
public class LRUCache {
class Node{
int key;
int data;
Node prev=null;
Node next =null;
public Node(int key, int data){
this.data = data;
this.key = key;
}
public int getKey(){
return key;
}
}
Node head = null;
Node end = null;
int capacity;
int len=0;
HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
public LRUCache(int capacity){
this.capacity = capacity;
}
public void setValue(int key, int value){
if(hm.containsKey(key)){
Node n = hm.get(key);
n.data = value;
remove(n);
setHead(n);
}else{
if(len<capacity){
Node n= new Node(key, value);
setHead(n);
len = len+1;
hm.put(key, n);
}else{
hm.remove(end.key);
remove(end);
Node n = new Node(key,value);
setHead(n);
hm.put(key, n);
}
}
}
public int getValue(int key){
if(hm.containsKey(key)){
Node n = hm.get(key);
remove(n);
setHead(n);
return n.data;
}
return -1;
}
private void setHead(Node n){
if(head == null){
head = n;
end =n;
}else{
head.prev = n;
n.next = head;
head = n;
}
}
private void remove(Node n){
Node pre = n.prev;
Node post = n.next;
if(pre==null)
head = post;
else
pre.next = post;
if(post == null)
end = pre;
else
post.prev=pre;
}
}
My appologies, Maintaining minimum heap will take nlogn time , we need to reduce the time, I think LinkedHashMap or similar data structure can be used for lru cache.In case of LinkedHashMap, insertion, and deletion both take O(1) time keeping in mind that whenever we use an element we make it to the head of linkedhashmap. This way the last element will be the least used and when inserting new element we can delete the last element and insert new one in its place.
Take a double linked list. The head will always contain the most recently used page & tail will contain the least recently page..
A hash where page number will be used for indexing will be taken. Whenever, a page fault occurs i.e. page is not in the memory[the hash slot will be empty], We will create a new node in DLL, put it in the head & store its pointer in the hash.
At any time, if a page needs to be referenced, it will be searched in the hash. If its there, we need to change at most 6 pointers to attach it at the head of DLL.
reqPage->next->prev=reqPage->prev;
reqPage->prev->next=reqPage->next;
reqPage->next=head;
reqPage->prev=NULL;
head->prev=reqPage;
head=reqPage;
import java.util.HashMap;
public class LRUCache {
class Node{
int key;
int data;
Node prev=null;
Node next =null;
public Node(int key, int data){
this.data = data;
this.key = key;
}
public int getKey(){
return key;
}
}
Node head = null;
Node end = null;
int capacity;
int len=0;
HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
public LRUCache(int capacity){
this.capacity = capacity;
}
public void setValue(int key, int value){
if(hm.containsKey(key)){
Node n = hm.get(key);
n.data = value;
remove(n);
setHead(n);
}else{
if(len<capacity){
Node n= new Node(key, value);
setHead(n);
len = len+1;
hm.put(key, n);
}else{
hm.remove(end.key);
remove(end);
Node n = new Node(key,value);
setHead(n);
hm.put(key, n);
}
}
}
public int getValue(int key){
if(hm.containsKey(key)){
Node n = hm.get(key);
remove(n);
setHead(n);
return n.data;
}
return -1;
}
private void setHead(Node n){
if(head == null){
head = n;
end =n;
}else{
head.prev = n;
n.next = head;
head = n;
}
}
private void remove(Node n){
Node pre = n.prev;
Node post = n.next;
if(pre==null)
head = post;
else
pre.next = post;
if(post == null)
end = pre;
else
post.prev=pre;
}
}
Use a doubly-linked list in combination with a HashMap. The HashMap should provide value lookup by key for your cache, in O(1) time. The HashMap should also contain a pointer to the corresponding node in the doubly-linked list so that when a key is accessed, the corresponding node in the linked list can be deleted from its current position and moved to the tail, which is the position for the most recently seen node. If you see a new element you haven't seen before (that is not in your HashMap), you add it to both the HashMap and the tail of the linked list. The linked list allows you to see which element expires next in O(1) time, and if the list exceeds the number of elements you want to cache, you delete the next-expiring element from both the linked list and the HashMap.
- eugene.yarovoi July 17, 2012All operations are in O(1) time (expected time, in the case of the HashMap).
If you need determinism, you can use a balanced tree sorted by key instead of the HashMap; this will be O(logN) for lookup, insert, and delete.