146. LRU Cache

https://leetcode.com/problems/lru-cache/

LinkedList implementation using timestamps: Time Limit Exceeded

Copy

class Node {
    int key;
    int val;
    int timestamp;
    Node(){}
    Node(int key, int val,int timestamp){
        this.key=key;
        this.val=val;
        this.timestamp=timestamp;
    }
}
class LRUCache {
    int capacity;
    int timestamp;
    LinkedList<Node> cache;
    
    public LRUCache(int capacity) {
        this.capacity=capacity;
        this.timestamp=-1;
        cache=new LinkedList<>();
    }
    
    public int get(int key) {
        for(int i=0;i<cache.size();i++){
            if(cache.size()>0&&cache.get(i).key==key){
                cache.get(i).timestamp=this.timestamp+1;
                int tmp=cache.get(i).val;
                cache.sort((Node n1,Node n2)->n1.timestamp-n2.timestamp);
                this.timestamp++;
                return tmp; 
            } 
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(cache.size()<this.capacity){
            for(int i=0;i<cache.size();i++){
                if(cache.get(i).key==key) cache.remove(i);
            }
            cache.add(new Node(key,value,++this.timestamp));
            cache.sort((Node n1,Node n2)->n1.timestamp-n2.timestamp);
        }else{
            boolean flag=false;
            for(int i=0;i<cache.size();i++){
                if(cache.get(i).key==key){
                    cache.remove(i);
                    flag=true;
                } 
            }
            if(flag==false) cache.removeFirst();
            cache.add(new Node(key,value,++this.timestamp));
            cache.sort((Node n1,Node n2)->n1.timestamp-n2.timestamp);
        }
    }
}
//   Your LRUCache object will be instantiated and called as such:
public class lc146{
    public static void main(String[] args) {
        LRUCache obj = new LRUCache(2);
        obj.put(2,1);
        obj.put(1,1);
        obj.put(2,3);
        obj.put(4,1);
        System.out.println("=> "+obj.get(1));
        System.out.println("=> "+obj.get(2));
    }
}

LinkedHashMap

Copy

class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    
    public LRUCache(int capacity) {
        cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    } 
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

Hashmap + DoubleLinkedList

Copy

class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        // head.prev = null;

        tail = new DLinkedNode();
        // tail.next = null;

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;

        // move the accessed node to the head;
        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            ++size;

            if (size > capacity) {
                // pop the tail
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                --size;
            }
        } else {
            // update the value.
            node.value = value;
            moveToHead(node);
        }
    }

    private void addNode(DLinkedNode node) {
        /**
         * Always add the new node right after head.
         */
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        /**
         * Remove an existing node from the linked list.
         */
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    private void moveToHead(DLinkedNode node) {
        /**
         * Move certain node in between to the head.
         */
        removeNode(node);
        addNode(node);
    }

    private DLinkedNode popTail() {
        /**
         * Pop the current tail.
         */
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}