Case study: Leetcode 146 LRU cache - Java

 Here is the link. 

	Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
	Implement the LRUCache class:
	LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
	int get(int key) Return the value of the key if the key exists, otherwise return -1.
	void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
	Follow up:
	Could you do get and put in O(1) time complexity?
	Example 1:
	Input
	["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
	[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
	Output
	[null, null, null, 1, null, -1, null, -1, 3, 4]
	Explanation
	LRUCache lRUCache = new LRUCache(2);
	lRUCache.put(1, 1); // cache is {1=1}
	lRUCache.put(2, 2); // cache is {1=1, 2=2}
	lRUCache.get(1); // return 1
	lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
	lRUCache.get(2); // returns -1 (not found)
	lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
	lRUCache.get(1); // return -1 (not found)
	lRUCache.get(3); // return 3
	lRUCache.get(4); // return 4
	Constraints:
	1 <= capacity <= 3000
	0 <= key <= 3000
	0 <= value <= 104
	At most 3 * 104 calls will be made to get and put.
	Algo: LinkedHashMap
	Map<Integer, ListNode> linkedHashMap
	private static class ListNode {
	int value = 0;
	ListNode prev = null;
	ListNode next = null;
	}
	when we get(key) a given value, I'll move the list node to the tail of our linkedlist
	when we put(key, value) - if that key is already in the map, we remove it first. We add a new node with this value to the tail of the linkedlist.
	After adding the new node into the structure, we look to see if map.size() > capacity. If map.size() is greater than capacioty, we remove the final node in the linked list.
	public static class LRUCache {
	public static final int NOT_FOUND = -1;
	private final int capacity;
	private final Map<Integer, Integer> map;
	public LRUCache(int capacity) {
	this.capacity = capacity;
	map = new LinkedHashMap<>(capacity * 2, 0.75f, true);
	}
	public int get(int key) {
	Integer value = map.get(key);
	if (value == null) return NOT_FOUND;
	return value.intValue();
	}
	public void put(int key, int value) {
	map.put(key, value);
	if (map.size() <= capacity) return;
	Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
	if (!iterator.hasNext()) return;
	iterator.next();
	}
	}

view raw LRUCach.Java hosted with ❤ by GitHub