Open
Description
Bug Report for https://neetcode.io/problems/lru-cache
Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.
I have a working solution for LRU cache from leetcode. However here in neetcode its giving NPE. Below is the code for LRU cache.
class LRUCache {
class Node{
int key;
int val;
Node next;
Node prev;
Node(int key, int value){
this.key=key;
this.val=value;
}
}
int capacity;
HashMap<Integer, Node> map;
Node head;
Node tail;
public LRUCache(int capacity){
this.capacity = capacity;
map = new HashMap<>();
head = new Node(-1,-1);
tail = new Node(-1,-1);
head.next=tail;
tail.prev=head;
}
private void removeNode(Node node){
node.prev.next =node.next;
node.prev=head;
node.next.prev = node;
head.next=node;
}
private void addToHead(Node node){
node.next=head.next;
head.next.prev=node;
}
public int get(int key) {
if(map.containsKey(key)){
//remove node
// add to head
//return value
Node curr = map.get(key);
removeNode(curr);
addToHead(curr);
return curr.val;
} else {
return -1;
}
}
public void put(int key, int value) {
// if key already exists
//remove from linked list
//add to head,
//update value.
if (map.containsKey(key)){
//remove as its most recently used now.
Node node = map.get(key);
removeNode(node);
//add to head
addToHead(node);
node.val=value;
}else{
if(map.size()==capacity){
// remove LRU
Node tailPrev = tail.prev;
removeNode(tailPrev);
//remove from map.
map.remove(tailPrev.key);
}
Node newNode = new Node(key,value);
map.put(key,newNode);
//add to head
addToHead(newNode);
}
}
}
Metadata
Metadata
Assignees
Labels
No labels