@@ -0,0 +1,2639 @@
+package com.freetymekiyan.algorithms.datastructures;%0A%0Aimport java.security.InvalidParameterException;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * Design and implement a data structure for Least Recently Used (LRU) cache.%0A * It should support the following operations: get and set.%0A * %3Cp%3E%0A * get(key) - Get the value (will always be positive) of the key if the key%0A * exists in the cache, otherwise return null. (get means use, so we need to update)%0A * %3Cp%3E%0A * set(key, value) - Set or insert the value if the key is not already present.%0A * When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.%0A */%0Apublic class LRUCache%3CK, V%3E %7B%0A%0A    private final int capacity;%0A    private Map%3CK, Node%3E cache;%0A    private Node dummyHead = new Node();%0A    private Node tail = new Node();%0A%0A%0A    public LRUCache(int capacity) %7B%0A        if (capacity %3C= 0) %7B%0A            throw new InvalidParameterException(%22Cache capacity should be larger than 0%22);%0A        %7D%0A        this.capacity = capacity;%0A        cache = new HashMap%3C%3E(capacity);%0A        dummyHead.next = tail;%0A        dummyHead.prev = null;%0A        tail.prev = dummyHead;%0A        tail.next = null;%0A    %7D%0A%0A    public void set(K key, V val) %7B%0A        if (cache.containsKey(key)) %7B%0A            Node node = cache.get(key);%0A            node.val = val;%0A            moveToHead(node);%0A        %7D else %7B%0A            Node newNode = new Node(key, val);%0A            addFirst(newNode);%0A            cache.put(key, newNode);%0A            if (cache.size() %3E capacity) %7B%0A                K toRemove = removeLast();%0A                cache.remove(toRemove);%0A            %7D%0A        %7D%0A    %7D%0A%0A    public V get(K key) %7B%0A        if (!cache.containsKey(key)) %7B%0A            throw new NullPointerException(%22This key is NOT in cache.%22);%0A        %7D%0A        Node node = cache.get(key);%0A        moveToHead(node);%0A        return node.val;%0A    %7D%0A%0A    private void moveToHead(Node node) %7B%0A        node.removeSelf();%0A        addFirst(node);%0A    %7D%0A%0A    private void addFirst(Node n) %7B%0A        n.prev = dummyHead;%0A        n.next = dummyHead.next;%0A%0A        n.next.prev = n;%0A        n.prev.next = n;%0A    %7D%0A%0A    private K removeLast() %7B%0A        K key = tail.prev.key;%0A        tail.prev.removeSelf();%0A        return key;%0A    %7D%0A%0A    class Node %7B%0A%0A        Node prev;%0A        Node next;%0A        K key;%0A        V val;%0A%0A        public Node() %7B%0A        %7D%0A%0A        public Node(K key, V val) %7B%0A            this.key = key;%0A            this.val = val;%0A        %7D%0A%0A        void removeSelf() %7B%0A            this.prev.next = this.next;%0A            this.next.prev = this.prev;%0A        %7D%0A    %7D%0A%7D%0A

add lru cache using generics