Does anyone solve it by using java? got TLE

Question

class LRUCache
{
int capacity;
Queue<Integer> queue = new LinkedList<Integer>();
Map<Integer, Integer> table = new HashMap<Integer, Integer>();
public LRUCache(int capacity) 
{    
    this.capacity = capacity;
}   
public int get(int key) 
{
    if(table.containsKey(key))
    {
        queue.remove(key);
        queue.offer(key);
        return table.get(key);
    }
    else return -1;
}
public void set(int key, int value) 
{
    if(table.size() == capacity)
    {
        table.remove(queue.poll());
    }
    if(table.containsKey(key)) 
    {
        table.put(key, value);
        queue.remove(key);
        queue.offer(key);
    }
    else
    {
        table.put(key, value);
        queue.offer(key);
    }
}
}

My idea is using queue to store the order of keys. Every time I finish using one key and then move the key to the tail. If the size is large than the capacity, remove the first key. My question is do I have to use double list? Does anyone use java to implement it?

Answer 1

The problem is your queue.remove(key) operation takes O(n) time, which is hardly efficient. To get accepted, you need to achieve constant time in both set and get operations.

To achieve constant time, you will need a table that maps the key to the LinkedList's node directly, so node deletion is a constant time operation. Although Java's internal LinkedList implementation is a Doubly Linked List, unfortunately it hides the implementation from you (which is a good practice by the way) so you are not able to access its nodes directly.

I am aware of two possible solutions in Java:

1. Use LinkedHashMap internally, which is considered as cheating -- LinkedHashMap is built to solve this kind of problem essentially.

2. Implement your own Doubly Linked List which is not hard, but could be tricky. On the bright side, this is a very good coding exercise.

Comments

Thanks, I will try both two ways. :)

---

LinkedHashMap is quite a good choice. Should be aware of trick: remove entry first before re-set,

---

Yeah, I realize that trick when I got wrong answer first time. :)

Answer 2

This is my java code that passes. It's a bit tricky to write a bug-free double link list implementation. Also the head of my list is the LRU element while the tail is the most recently used element.

public class LRUCache {

    public LRUCache(int capacity) {
        mCapacity = capacity;
    }

    public int get(int key) {

        if (!mKeyValueNodeMap.containsKey(key))
            return -1;

        Node node = mKeyValueNodeMap.get(key);

        // move the node to the end of link list if it's not the end
        Node prevNode = node.prev;
        Node nextNode = node.next;
        if (nextNode != null) {
            if (prevNode == null) { // the head node
                mHead = nextNode;
            } else {
                prevNode.next = nextNode;
            }
            nextNode.prev = prevNode;

            node.prev = mTail;
            node.next = null;
            mTail.next = node;
            mTail = node;
        }

        return node.val;
    }

    public void set(int key, int value) {

        if (mKeyValueNodeMap.containsKey(key)) {
            get(key); // only to move it to the tail
            mKeyValueNodeMap.get(key).val = value;
        } else {        
            Node node = new Node(key, value);

            // invalidate the LRU item, meaning remove the head element
            if (mKeyValueNodeMap.size() >= mCapacity) {
                if (mHead != null) {
                    Node oldHead = mHead;
                    mHead = mHead.next;
                    oldHead.next = null;
                    if (mHead != null) // it could be only one item
                        mHead.prev = null;
                    mKeyValueNodeMap.remove(oldHead.key);
                }
            }

            // insert the new value
            if (mHead == null) {
                mHead = node;
                mTail = node;
            } else {
                mTail.next = node;
                node.prev = mTail;
                mTail = node;
            }
            mKeyValueNodeMap.put(key, node);
        }
    }

    private class Node {

        int key;
        int val;
        Node prev = null;
        Node next = null;
        Node(int k, int v) {
            key = k;
            val = v;
        }   
    }

    HashMap<Integer, Node> mKeyValueNodeMap = new HashMap<Integer, Node>();
    Node mHead = null;
    Node mTail = null;
    int mCapacity = 0;
}

Answer 3

I implemented the cache with three HashMap in Java and passed the OJ.

The idea is to assign each operation an integer number as a counter. So each key / value pair is always associated with its counter. The counter for the least used key / value pair is maintained.

Specifically, the three hashmaps are:

• HashMap data_ stores key : value pair

• HashMap keyOrder_ stores key : counter pair

• HashMap orderKey_ stores counter : key pair

The code is here: https://github.com/tuliren/myleetcode/blob/master/LRUCache.java

Comments

Nice idea, but could you explain by updating your answer on the complexity of your algorithm? Please correct me if I'm wrong, but it seems that deleteLeastUsed takes O(n) time, where n is the capacity.

---

In worst case, yes, delete a key / value pair could take O(n) time. But I checked the code and it seems that the worst case only occurs every n operations. Therefore, the amortized cost is probably still O(1).

Answer 4

Below is my code passed. Generally, use HashMap as the data structure to store key-value pair and one tricky point is to use a class which contains "nextKey" and "previousKey" as the data structure for value instead of simple int value. So that we can get a "LinkedHashMap

public class LRUCache {
  class valueSet {
        int value;
        int next;
        int previous;

        valueSet(int value) {
            this.value = value;
            next = -1;
            previous = -1;
        }
    }

    private int capacity;
    private HashMap<Integer, valueSet> cache;
    private int currentLength;
    private int head;
    private int tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<Integer, valueSet>();
        this.currentLength = 0;
        this.head = -1;
        this.tail = -1;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            moveToHead(key);
            return cache.get(key).value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (cache.containsKey(key)) {
            cache.get(key).value = value;
            moveToHead(key);
        } else {
            valueSet newValue = new valueSet(value);
            if (currentLength < capacity) {
                cache.put(key, newValue);
                currentLength++;
                addToHead(key);
            } else {
                int newTail = cache.get(tail).previous;
                cache.remove(tail);
                tail = newTail;
                cache.put(key, newValue);
                addToHead(key);
            }
        }
    }

    private void moveToHead(int key) {
        if (head != key) {
            valueSet newHead = cache.get(key);
            cache.get(newHead.previous).next = newHead.next;

            if (tail != key) {
                cache.get(newHead.next).previous = newHead.previous;
            }
            else tail = newHead.previous;
            newHead.next = head;
            newHead.previous = -1;
            cache.get(head).previous = key;
            head = key;
        }
    }

    private void addToHead(int key){
        valueSet newValue = cache.get(key);
        newValue.next = head;
        if(currentLength > 1){
            cache.get(head).previous = key;
        }
        head = key;
        if(currentLength == 1)
            tail = key;
    }


}

Comments

Could you please format your code? Since the last } is out of your code box.