You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
* Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: getValue and setKeyValue.
*
* getValue(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
* setKeyValue(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.
*
* Ref: Cracking the code interview: Moderate 16.25, Page 185
*/
publicclassLruCache {
publicclassNode {
Nodeprev, next;
intkey;
Stringval;
publicNode(intk, Stringv) {
this.key = k;
this.val = v;
prev = next = null;
}
}
Nodehead;
Nodetail;
privateMap<Integer, Node> map = newHashMap<>();
privateintsize;
publicLruCache(intsize){
this.size = size;
}
/* Get Value from key and mark it as most recently used */
publicStringgetValue(intkey){
Nodeitem = map.get(key);
if(item == null){
returnnull;
}
/* If item is not head, move the item front of list to mark as Most recently used. */
if(item != head) {
removeFromLinkedList(item);
insertAtFrontOfLinkedList(item);
}
returnitem.val;
}
/* Remove Node from a Linked List */
publicvoidremoveFromLinkedList(Nodenode){
if(node == null){
return;
}
//If node is head, make next node as head
if(node == head){
head = head.next;
}
//If node is tail, make previous node as tail
if(node == tail){
tail = tail.prev;
}
if(node.prev != null){
node.prev.next = node.next;
}
if(node.next != null){
node.next.prev = node.prev;
}
}
/* Insert Node at front of linked list */
publicvoidinsertAtFrontOfLinkedList(Nodenode){
if(node == null){
return;
}
if(head == null){
head = node;
tail = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
/* Remove key/value pair from cache, deleting from hash table and linked list. */
publicbooleanremoveKey(intkey){
Nodeitem = map.get(key);
removeFromLinkedList(item);
map.remove(key);
returntrue;
}
/* Put key,value pair in cache. Remove old values for keys if necessary. Insert pairs in linked-list and hash-table */
publicvoidsetKeyValue(intkey, Stringvalue){
/* Remove key if already there */
removeKey(key);
/* If full remove recently used item. */
if(map.size() >= size && tail != null){
removeKey(tail.key);
}
/* Insert new node. */
Nodenode = newNode(key,value);
insertAtFrontOfLinkedList(node);
map.put(key,node);
}
/* Print Doubly Linked List */
publicstaticvoiddisplay(Nodenode){
System.out.print("Null <---> ");
while(node!=null){
System.out.print(node.val+ " <---> ");
node = node.next;
}
System.out.println("Null");
}
publicstaticvoidmain(String[] args) {
LruCachecache = newLruCache(5);
cache.setKeyValue(1,"Book");
cache.setKeyValue(2,"Dress");
cache.setKeyValue(3,"Shoe");
cache.setKeyValue(4,"Sock");
cache.setKeyValue(5,"Pencils");
cache.setKeyValue(6,"Pens");
System.out.println("Value is : "+cache.getValue(2));
