Blog Details

LRU Cache – LeetCode 146

1. Description

Design and Implement a data structure for LRU cache. It should support get and put.

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

Implement it by O(n) time complexity for both operations.

2. Examples

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

3. Solution

3.1 How LRU works?

3.2 Which data structure to choose?

3.3 Code

  • CacheNode.java
public class CacheNode {
	int key;
	int val;
	CacheNode next;
	CacheNode prev;
}
  • LRUCache.java
import java.util.Hashtable;

public class LRUCache {
	private Hashtable<Integer, CacheNode> lookUpTable;
	
	// Here head and tail are just dummy nodes, not saving data.
	private CacheNode head;
	private CacheNode tail;
	private int totalNodesInCache;
	private int maxCapacity;
	
	public LRUCache(int capacity) {
		this.lookUpTable = new Hashtable<Integer, CacheNode>(capacity);
		this.maxCapacity = capacity;
		totalNodesInCache = 0;
		
		this.head = new CacheNode();
		this.tail = new CacheNode();
		
		this.head.prev = null;
		this.head.next = this.tail;
		this.tail.next = null;
		this.tail.prev = this.head;
	}
	
	public int get(int key) {
		CacheNode node = this.lookUpTable.get(key);
		boolean nodeFoundInCache = node != null;
		if (!nodeFoundInCache) {
			return -1;
		}
		
		// move this node to head
		moveNodeToHead(node);
		return node.val;
	}
	
	
	public void put(int key, int value) {
		CacheNode node = lookUpTable.get(key);
		boolean nodeInCache = node != null;
		if (!nodeInCache) {
			CacheNode newNode = new CacheNode();
			newNode.key = key;
			newNode.val = value;
			
			// put it into lookUpTable
			lookUpTable.put(key, newNode);
			
			// Add it to Cache list
			addToHead(newNode);
			
			// total item increased
			totalNodesInCache ++;
			
			if(totalNodesInCache > maxCapacity) {
				// remove the last node from the cache list and also remember update the lookUpTable
				CacheNode lastNodeInCache = this.tail.prev;
				removeNode(lastNodeInCache);
				
				lookUpTable.remove(lastNodeInCache.key);
				--totalNodesInCache;
			}
			
		} else {
			node.val = value;
			moveNodeToHead(node);
		}
	}
	
	private void moveNodeToHead(CacheNode node) {
		removeNode(node);
		addToHead(node);
	}
	
	/**
	 * Remove the node from list
	 * @param node
	 */
	private void removeNode(CacheNode node) {
		CacheNode prevNode = node.prev;
		CacheNode nextNode = node.next;
		prevNode.next = nextNode;
		nextNode.prev = prevNode;
	}	
	private void addToHead(CacheNode node) {
		node.prev = this.head;
		node.next = this.head.next;
		this.head.next.prev = node;
		this.head.next = node;
	}	
}
  • LRUCacheTest.java
import org.junit.Test;

public class LRUCacheTest {
	@Test
	public void testLRU() {
		LRUCache cache = new LRUCache(2);
		cache.put(1, 1);
		cache.put(2, 2);
		int val1 = cache.get(1);
		System.out.println("key == 1, value == " + val1);
		cache.put(3, 3);
		int val2 = cache.get(2);
		System.out.println("Key == 2, value == " + val2);
	}
}