LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

这道题粗看一下觉得很简单,只用fifo似乎就可以,但是fifo 找key-value pair太慢,所以需要用fifo(用doubly linked list实现,因为我们需要将最新用过的加到head,而删除需要从tail)和hashmap一起用才行。

我们自己定义一个class node,每个node有向前和向后的指针,并且记录一个value和一个key的值。
我们自己定义的doubly linked list需要有这样几个功能。
1. removeKey,将某个node从linkedlist里删除出去。
2. addkey,将某个node加入到linkedlist尾部。
3. removeTail,将某个node从尾部删除,这个和remove key不一样,因为不知道key是多少。
4. 如果我们调用了get函数,那么getkey的相应node应该被移到开头,我们用removeKey+addKey来实现即可。

我们的办法是用一个hashmap,将每个key map到一个node,这样removekey就是O(1)的复杂度了
addKey本来就是O(1)的复杂度。
removeTail因为每个tail里存有key的信息,所以和removekey一样,也是O(1)的复杂度。

主要就是注意实现三个函数的时候linkedlist为空和为1的情况。

public class LRUCache {
    HashMap<Integer, Node> valueMap = new HashMap<Integer, Node>(); // key value
    Node head = null;
    Node tail = null;
    int capacity, curr;
    public LRUCache(int capacity) {
        this.capacity = capacity; // current content
        curr = 0;
    }
    
    public int get(int key) {
        if (!valueMap.containsKey(key))
            return -1;
        else
        {
            int result = valueMap.get(key).val;
            removeKey(key);
            addKey(key, result);
            return result;
        }
    }
    
    public void set(int key, int value) {
        if (valueMap.containsKey(key))
        {
            removeKey(key);
            addKey(key, value);
            valueMap.get(key).val = value;
        }
        else
        {
            if (curr < capacity) // add a new key
            {
                curr++;
                addKey(key, value);
            }
            else
            {
                removeTail();
                addKey(key, value);
            }
        }
    }
    
    public void removeTail()
    {
        valueMap.remove(tail.key);
        if (tail == head)
        {
            tail = null;
            head = null;
        }
        else
        {
            Node n = tail.pre;
            tail.pre = null;
            n.next = null;
            tail = n;
        }
        
    }
    
    public void removeKey(int key)
    {
        Node n = valueMap.get(key);
        if (n == head && n == tail) // if only 1 key
        {
            head = null;
            tail = null;
        }
        else if (n == head) //remove head
        {
            head = n.next;
            n.next = null;
            head.pre = null;
        }
        else if (n == tail)
        {
            tail = n.pre;
            n.pre.next = null;
            n.pre = null;
        }
        else
        {
            n.pre.next = n.next;
            n.next.pre = n.pre;
        }
        valueMap.remove(new Integer(key));
    }
    
    
    public void addKey(int key, int value) // add key to head, regardless of size
    {
        Node n = new Node();
        n.val = value;
        n.key = key;
        if (head == null) // if empty 
        {
            head = n;
            tail = n;
        }
        else
        {
            n.next = head;
            head.pre = n;
            head = n;
        }
        valueMap.put(key, n);
    }
}

class Node
{
    Node next;
    Node pre;
    int val;
    int key;
}

update更efficient的code,其实这道题就是怎样在constant的时间内将linkedlist中的一个数找到并移到头部,singlelinkedlist是不行的,因为定位加移动到头部要划掉On时间,太慢了,所以办法是用doublylinkedlist。这样用hashmap找到listnode以后直接移动到头部,原来位置的头尾接好,constant time。要注意listnode里不仅要存value,还要存key,因为你在删除尾部的时候,也要删除hashMap里的entry,想要constant时间,必须要有key才行。Notice the helper pointer here is actually the tail pointer.

public class LRUCache {
    HashMap<Integer, DoubleLinkedListNode> data = new HashMap<Integer, DoubleLinkedListNode>();
    int cap;
    int count = 0;
    DoubleLinkedListNode head = null;
    DoubleLinkedListNode helper;
    public LRUCache(int capacity) {
        cap = capacity;
        helper = new DoubleLinkedListNode(-1,-1);
        head = helper;
    }
    
    public int get(int key) {
        if (data.containsKey(key)) {
            //move double LinkedList to head
            DoubleLinkedListNode n = data.get(key);
            if (!(n == head)) {  // if it is the head, do nothing
                n.pre.next = n.next;
                n.next.pre = n.pre;
                head.next = n;
                n.pre = head;
                n.next = null;
                head = n;
            }
            return n.val;
        }
        return -1;
    }
    
    public void set(int key, int value) {
        if (data.containsKey(key)) {
            //move double LinkedList to head
            DoubleLinkedListNode n = data.get(key);
            if (!(n == head)) {  // if it is the head, do nothing
                n.pre.next = n.next;
                n.next.pre = n.pre;
                head.next = n;
                n.pre = head;
                n.next = null;
                head = n;
            }
            n.val = value;
        }
        else {
            if (count == cap) { // remove the tail
                data.remove(helper.next.key);
                if (helper.next == head) {// if only one element;
                    head = helper;
                    helper.next = null;
                }
                else {
                    helper.next = helper.next.next;
                    helper.next.pre = helper;
                }
                count--;
                
            }
            DoubleLinkedListNode n = new DoubleLinkedListNode(key, value);
            data.put(key, n);
            head.next = n;
            n.pre = head;
            head = n;
            count++;
        } 
    }
    
    public class DoubleLinkedListNode {
        DoubleLinkedListNode pre;
        DoubleLinkedListNode next;
        int key;
        int val;
        public DoubleLinkedListNode(int k, int v) {
            key = k;
            val = v;
            pre = null;
            next = null;
        }
    }
}

Use tail and head pointer. Use the get method to do modification and move the new value to the head.

public class LRUCache {
    HashMap<Integer, DoubleLinkedListNode> data = new HashMap<Integer, DoubleLinkedListNode>();
    int cap;
    int count = 0;
    DoubleLinkedListNode head, tail;
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int get(int key) {
        if (data.containsKey(key)) {
            //move recently accessed node to the head of the list
            DoubleLinkedListNode curr = data.get(key);
            if (curr == head)
                return curr.val;
            if (curr == tail) {
                tail = curr.pre;
            }
            else {
                curr.next.pre = curr.pre;
            }
            curr.pre.next = curr.next;
            //insert to the head
            curr.next = head;
            curr.pre = null;
            head.pre = curr;
            head = curr;
            return curr.val;
        }
        return -1;
    }
    
    public void set(int key, int value) {
        if (!data.containsKey(key)) {
            DoubleLinkedListNode n = new DoubleLinkedListNode (key, value);
            if (count == 0) {
                head = n;
                tail = n;
                data.put(key, n);
                count++;
            }
            else if (count < cap) {
                n.next = head;
                n.pre = null;
                head.pre = n;
                head = n;
                data.put(key, n);
                count++;
            }
            else { // if count == capacity
                n.next = head;
                n.pre = null;
                head.pre = n;
                head = n;
                //remove tail
                data.remove(tail.key);
                tail = tail.pre;
                tail.next = null;
                data.put(key, n);
            }
        }
        else { // use the get method to move the new added value to the head
            data.get(key).val = value;
            get(key);
        }
    }
    
    public class DoubleLinkedListNode {
        DoubleLinkedListNode pre, next;
        int key, val;
        public DoubleLinkedListNode(int k, int v) {
            key = k;
            val = v;
        }
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s