Problem
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.
The functions get and put must each run in O(1) average time complexity.
Testcases
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
Initial Result
Time spent: 30 min
Fail. Erroring out in the insert_front helper function. Not debugging this one and skipping ahead to solution to verify cache structure. I suspect there is one tricky edge case to tackle.
Initial Approach
I had the doubly-linked list and hashmap solution spoiled for me, so I mostly implemented that. I didn’t read the requirements fully, so I had to modify for maintaining both a key and value. I’m stopping at the point where I’m uncertain about including the key AND value in the node (which seems unnecessary in an ideal solution).
What I Missed
You can just store the key in the node (a la “you can just do things”). Additionally, the helper functions can focus on nodes alone and not any cache manipulation.
Approach to the Solution
There are multiple ways to use the helper functions, but due to the structure of the nodes (containing prev and next pointers) it is easiest to just pass them nodes themselves (but choosing to pass a key won’t hurt the problem at all). We can structure get as just remove, add, and return the relevant value. Additionally, we can create put as something that always removes (if possible) and then inserts while adding to the cache. We also handle cache removal here while wrapping up both parts of LRU removal (the node and the cache) in a comparison between capacity and the length of the cache.
Key Takeaways
Draw out state and also write down different possibilities for where to manipulate state (in or outside of functions). Try to isolate this when possible (helpers only touch the doubly-linked list).