Leetcode 146. LRU Cache

[medium][Amazon]

LRU Cache - LeetCode

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.

[Think]

1. this is a system design question, have to create class, function and data structure.
2. this question we want to create a double linkedlist, and apply two main function get and put.
3. to do that, we have to create another four method for our double linkedlist node. addNode, removeNode, moreToHead, popTail.
4. using hashtable to store key and doublelinkedNode — cache
5. addNode — have to connect a new Node to head in both direction
6. removeNode- have to create another DLinkedNode to skip the node
7. moveToHead- removeNode and addNode
8. popTail — get the tail.pre, and removeNode, return the popTail part
9. capacity — create a data structire for capacity and default the setting for head and tail
10. get — if we can find the key in hashtable- cache; moveToHead the node and return the node.value
11. put — if the key already exist, we update the value and moveToHead; if we don’t have the key, create another newNode and add its key and value into cache.
12. if the count > capacity, have to poptail and make sure have enought room for the newNode

[Note]

1. I tried hard to understand the code — be patient
2. pointer pre and post are very confuse, draw it on paper will help understand
3. build a code structure first and it will help to find out what should do next
4. it’s a good question for system deisgn — objected-oriented
5. this — is what we are working on, so everytime want to call a function, have to make sure we adjust on “this”
6. be careful for the typo on “DLinkedNode”
7. Happy coding