LRU cache question

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

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

Solution

To achieve $O(1)$ time for both get and set, we first need the hashmap to keep the record. 

A problem happens when trying to keep track of what's least used to evict.

For that, we can use a priority queue and keep the least used element in the first.

One thing that confused me is whether updating the same value (put with the existing key) is considered to be used. I initially thought it was not. That delayed the time to debug. Also, we need to think about the corner case as well.

Here is the rough algorithm:

- get(k)

 check if k exists in the hashmap.

 if so return the value

 move the k to the end of the priority queue

 

 return -1 if not found

- put (k, v)

 if k exists in the hashmap

   get the value element

   update the value

   move the k to the end of the priority queue

 if k is the key to the hashmap

    if the queue is at capacity, remove the element at the head from the priority queue

    add k, v to the hashmap

    add k to the end of the priority queue

   

UPDATE 03-09-2023:

Here is the python solution

Practice statistics

15 mins: algorithm

12 mins: to code (with bugs)

10 mins: to debug