Leetcode solution 146. LRU Cache

Problem Statement 

Design and implement a data structure for Least Recently Used (LRU) 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 reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

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

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

The LRU cache has become an absolute standard interview question that we have to know how Java's LinkedHashMap or Python's OrderedDict works under the cover (A doubly linked list and a hashmap). I would actually recommend implementing a doubly linked list + hashmap solution in real interviews.

Follow up is how to implement a least frequent cache (LFU)?

• A doubly linkedlist + hashmap + A min heap (to count), however, both get and put would be O(LgN) since the heap would be modified due to the frequency increased by 1
• A doubly linkedlist + hashmap + ArrayList<Frequency, doubly linked list), Node structure would also carry a Frequency field.  For each frequency, we keep track of the elements and move them around when accessed. Get would be O(1), Put could potentially be worst case unbounded (we have to loop from frequency 0 to integer.max_value), or could be optimized to O(N)

Solutions

Using LinkedHashMap

Time Complexity: O(1) for both get and set
Space Complexity: O(N) Where N is the number of items inserted

Using Doubly LinkedList & Hashmap

Time Complexity: O(1) for both get and set
Space Complexity: O(N) Where N is the number of items inserted

References

• Leetcode official solution