146. LRU Cache
Design and implement a data structure for . It should support the following operations: 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. Follow up:
Could you do both operations in O(1) time complexity?Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // returns 1cache.put(3, 3); // evicts key 2cache.get(2); // returns -1 (not found)cache.put(4, 4); // evicts key 1cache.get(1); // returns -1 (not found)cache.get(3); // returns 3cache.get(4); // returns 4
Solution:
Cache all nodes in a DoubleLinkedList. Always pop out from the left, and add from the right.
Use a map to map key to a node.
class LRUCache { private int capacity; private int count = 0; private Map cacheMap = new HashMap<>(); private CacheNode LEFT = new CacheNode(0, 0); private CacheNode RIGHT = new CacheNode(0, 0); public LRUCache(int capacity) { this.capacity = capacity; LEFT.right = RIGHT; RIGHT.left = LEFT; } public int get(int key) { CacheNode node = cacheMap.get(key); if (node == null) { return -1; } else { removeNode(node); addNewNode(node); return node.value; } } public void put(int key, int value) { if (capacity == 0) return; CacheNode orig = cacheMap.get(key); CacheNode n = new CacheNode(key, value); addNewNode(n); //add new node to the right cacheMap.put(key, n); if (orig != null) { removeNode(orig); //remove original node. return; } //if capacity is not full if (count < capacity) { ++count; return; } CacheNode evict = LEFT.right; cacheMap.remove(evict.key); removeNode(evict); //removeNode last node. } private void removeNode(CacheNode node) { CacheNode pre = node.left; CacheNode next = node.right; pre.right = next; next.left = pre; } //Add a new node, add it to the end/Right private void addNewNode(CacheNode node) { node.left = RIGHT.left; node.right = RIGHT; RIGHT.left.right = node; RIGHT.left = node; }}class CacheNode { CacheNode left = null; CacheNode right = null; int key = 0; int value = 0; CacheNode(int key, int value) { this.key = key; this.value = value; }}
460. LFU Cache
Design and implement a data structure for cache. It should support the following operations: 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 reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted. Follow up:
Could you do both operations in O(1) time complexity?Example:
LFUCache cache = new LFUCache( 2 /* capacity */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // returns 1cache.put(3, 3); // evicts key 2cache.get(2); // returns -1 (not found)cache.get(3); // returns 3.cache.put(4, 4); // evicts key 1.cache.get(1); // returns -1 (not found)cache.get(3); // returns 3cache.get(4); // returns 4 This is just an extension of LRU. LFU is just a map of LRU keyed by the frequency!
/** * !!! Note that both get and put will increase frequency by 1 !!! */class LFUCache { private int _capacity; private int _count = 0; //To capture the minimum frequency count in the LFU cache //Alternatively, we can link all LRU cache together. private int _leastCount = 0; private Map frequencyMap = new HashMap<>(); private Map keyMap = new HashMap<>(); public LFUCache(int capacity) { _capacity = capacity; } public int get(int key) { CacheNode node = keyMap.get(key); if (node == null) { return -1; } increaseFreq(node); return node.value; } //remove node from current level and move it to the next level private void increaseFreq(CacheNode node) { LRUCache currentCache = frequencyMap.get(node.count); currentCache.removeNode(node); if (node.count == _leastCount && currentCache.isEmpty()) { ++_leastCount; //we are moving this node to next level } ++node.count; LRUCache nextCache = frequencyMap.computeIfAbsent(node.count, (x) -> new LRUCache()); nextCache.addNewNode(node); } public void put(int key, int value) { CacheNode node = keyMap.get(key); if (node != null) { node.value = value; increaseFreq(node); return; } LRUCache zeroFreqCache = frequencyMap.computeIfAbsent(0, (x) -> new LRUCache()); CacheNode newNode = new CacheNode(key, value, 0); zeroFreqCache.addNewNode(newNode); keyMap.put(key, newNode); if (_count < _capacity) { ++_count; } else { LRUCache cacheToEvict = frequencyMap.get(_leastCount); CacheNode nodeToEvict = cacheToEvict.LEFT.right; keyMap.remove(nodeToEvict.key); cacheToEvict.removeNode(nodeToEvict); } _leastCount = 0; }}class LRUCache { public final CacheNode LEFT = new CacheNode(0, 0, 0); public final CacheNode RIGHT = new CacheNode(0, 0, 0); public LRUCache() { LEFT.right = RIGHT; RIGHT.left = LEFT; } public void removeNode(CacheNode node) { CacheNode pre = node.left; CacheNode next = node.right; pre.right = next; next.left = pre; } public void addNewNode(CacheNode node) { node.left = RIGHT.left; node.right = RIGHT; RIGHT.left.right = node; RIGHT.left = node; } public boolean isEmpty() { return LEFT.right == RIGHT; }}class CacheNode { CacheNode left = null; CacheNode right = null; int key; int value; int count; CacheNode(int key, int value, int count) { this.key = key; this.value = value; this.count = count; }}