Does anyone solve it by using java? got TLE


  • 1
    B
    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?


  • 7

    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.


  • 0
    B

    Thanks, I will try both two ways. :)


  • 0
    J

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


  • 5
    X

    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;
    }

  • 0
    T

    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


  • 0

    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.


  • 1
    Y

    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;
        }
    
    
    }

  • 0
    B

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


  • 0
    S

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


  • 0
    T

    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).


  • 0
    R

    it can also be done using two maps,I have implemented using C++,accepted by OJ.

    std::unordered_map<key,counter>
    std::map<counter,object>, object stores value and key.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.