Why Time Limit Exceeded issue?


  • 1
    L

    Has one map to save the key/ value items; value is encapsulated in CacheItem. Uses another self-developed LRUList -- a linked list to record
    the least recent used "key". The head of the list is the least recently used one.





    Idea goes like this:

    1. when insert the new key/value pair: a) add new key/value to the map; b) append the one node to LRUList;

    2. when get the value: a) hit the map for the value; b) remove then add the corresponding node to LRUList.



      Why still get Time Limit Exceeded since LRUList is the linked list?

    Thanks.

    public class LRUCache
    {
    	private int capacity;
    	
    	private LRUList nodes = null;
    
    	// save cached items, key/value pair
    	private Map<Integer, CacheItem> cache = null;
    	
    	public LRUCache(int capacity)
    	{
    		this.capacity = capacity;
    		cache = new HashMap<Integer, CacheItem>(capacity);
    		nodes = new LRUList();
    	}
    
    	public int get(int key)
    	{
    		// hit the map.
    		CacheItem one = cache.get(Integer.valueOf(key));
    		if (one == null)
    		{
    			System.out.println("miss key: " + key);
    			return -1;
    		}
    
    		// touch the existing key/value by remove first then add again.
    		nodes.touch(one.node);
    
    		System.out.println("get key: " + key);
    		return one.value;
    	}
    
    	public void set(int key, int value)
    	{
    		int currentSize = cache.size();
    		if (currentSize < capacity)
    		{
    			// add to the LRUList then insert to the map.
    			CacheItem one = new CacheItem(value, nodes.add(key));
    			cache.put(Integer.valueOf(key), one);
    
    			System.out.println("add new: " + key);
    			return;
    		}
    
    		// get first item from nodes. the head of LRUList is the least used one.
    
    		QueueNode head = nodes.remove();
    		cache.remove(head.key);
    		System.out.println("remove head: " + head.key);
    
    		// add to the LRUList then insert to the map.
    		cache.put(Integer.valueOf(key), new CacheItem(value, nodes.add(key)));
    
    		System.out.println("add new: " + key);
    	}
    	
    	/**
    	 * The list to record the least/most recently used key. The head of the list is least one. 
    	 * The tail of the list is the most used one.
    	 * 
    	 * The list  is a two-way linked one.
    	 */
    	
    	static class LRUList
    	{
    		private QueueNode head;
    		private QueueNode tail;
    
    		public QueueNode add(int key)
    		{
    			QueueNode item = new QueueNode(key);
    			return add(item);
    		}
    
    		/**
    		 * 
    		 */
    		
    		private QueueNode add(QueueNode e)
    		{
    			if (head == null)
    			{
    				head = tail = e;
    			}
    			else
    			{
    				tail.next = e;
    				e.previous = tail;
    				tail = e;
    
    				if (tail.previous == null)
    				{
    					tail.previous = head;
    					head.next = tail;
    				}
    			}
    
    			return tail;
    		}
    
    		private QueueNode remove(QueueNode e)
    		{
    			if (e.previous == null)
    				head = e.next;
    			else
    				e.previous.next = e.next;
    
    			if (e.next == null)
    				tail = e.previous;
    			else
    				e.next.previous = e.previous;
    
    			//clear the related fields
    			e.previous = null;
    			e.next = null;
    			return e;
    		}
    
    		public QueueNode remove()
    		{
    			return remove(head);
    		}
    
    		public void touch(QueueNode e)
    		{
    			moveToTail(e);
    		}
    
    		private void moveToTail(QueueNode e)
    		{
    			remove(e);
    			add(e);
    		}
    
    		private void dumpQueue()
    		{
    			System.out.print("LRU queue : ");
    			
    			QueueNode e = head;
    			while (e!=null)
    			{
    				System.out.print(e.key +  "    ");
    				e = e.next;
    			}
    
    			System.out.println("");
    		}
    	}
    	
    	static class QueueNode
    	{
    		private int key;
    		private QueueNode previous;
    		private QueueNode next;
    
    		public QueueNode(int key)
    		{
    			this.key = key;
    		}
    	}
    	
    	/**
    	 * The value in the map. Used to save value and node in LRUList.
    	 *
    	 */
    	
    	private static class CacheItem
    	{
    		private int value;
    		private QueueNode node;
    
    		CacheItem(int value, QueueNode node)
    		{
    			this.value = value;
    			this.node = node;
    		}
    	}
    

    }


  • 0
    L

    Know the reason. Never put system.out in codes... Silly..


Log in to reply
 

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