Lru Cache

                                            
class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        } else {
            // Move the key to the front of the list
            keyList.splice(keyList.begin(), keyList, cache[key].second);
            return cache[key].first;
        }
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // Update the value if the key exists
            cache[key].first = value;
            keyList.splice(keyList.begin(), keyList, cache[key].second);
        } else {
            // Add the key-value pair
            if (cache.size() >= cap) {
                int deleteKey = keyList.back();
                cache.erase(deleteKey);
                keyList.pop_back();
            }
            keyList.push_front(key);
        }
        cache[key] = {value, keyList.begin()};
    }
    
private:
    unordered_map<int, pair<int, list<int>::iterator>> cache;
    list<int> keyList;
    int cap;
};

                                            
class LRUCache {
    private Map<Integer, Integer> map;
    private LinkedList<Integer> list;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            list.removeFirstOccurrence(key);
            list.addFirst(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            list.removeFirstOccurrence(key);
        } else if (list.size() >= capacity) {
            map.remove(list.removeLast());
        }

        map.put(key, value);
        list.addFirst(key);
    }
}

                                            
class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.cache = {}
        self.key_order = []

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.cache:
            self.key_order.remove(key)
            self.key_order.append(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.cache:
            self.key_order.remove(key)
        elif len(self.cache) == self.capacity:
            LRU_key = self.key_order.pop(0)
            del self.cache[LRU_key]

        self.cache[key] = value
        self.key_order.append(key)

To solve this coding challenge of designing and implementing an LRU (Least Recently Used) cache, you'll need to create a data structure that adheres to specific constraints: it must store key-value pairs, offer O(1) average time complexity for both retrieving a value from the cache and inserting a new key-value pair, and manage the size of the cache such that it does not exceed a defined capacity. If the cache’s size exceeds this capacity constraint, it must remove the least recently used (LRU) item before adding a new key-value pair.

Explanation

The LRU Cache is essential for scenarios where we need quick access to frequently accessed data but within a capacity limit. To manage the cache efficiently, we need an underlying data structure that supports fast look-up, add, and delete operations (hash table) and another one to keep track of the access order (doubly linked list).

Key Points:

Hash Table : Allows us to store key-value pairs for quick access.
Doubly Linked List : Keeps track of the order in which keys are accessed, with the most recently accessed key moving to the front and the least recently accessed one moving to the end. This property is crucial for determining which key to evict when the cache exceeds its capacity.
Capacity Handling : Ensures that once the cache reaches its capacity, the least recently used item is removed to make space for new entries.

Pseudocode Details:

Here is the detailed step-by-step pseudocode explanation along with the pseudocode itself.

Pseudocode Structure and Detailed Steps:

Initialization:

When initializing, we need to maintain the capacity and the data structure for the cache.

                                            
# LRUCache class initialization
initialize LRUCache with capacity:
set self.capacity to the given capacity   # Store the maximum size of the cache
create an empty dictionary self.cache     # To store key-value pairs
create an empty list self.key_order       # To keep track of the usage order of keys

Get Method:

To retrieve a value based on the key:

Check if the key exists in the cache.
If it does, update its position to reflect a recent access.
Return the value.
If the key doesn’t exist, return -1.

                                            
# Method to fetch data by key
method get(key):
if key exists in self.cache:               # Check if the key is in the cache
remove key from self.key_order         # This updates the key's position in the order
append key to the end of self.key_order  # Place key at the end to mark it as recently used
return value corresponding to key from self.cache # Return the cached value
else:
return -1                               # Key doesn't exist in cache

Put Method:

To insert or update key-value pairs:

If the key already exists, just update its value and reorder it as most recently used.
If the key does not exist:

Check if the current cache size is at capacity.
If it is, remove the least recently used item (the first item in the key order list).
Insert the new key-value pair and update the order list.

                                            
# Method to insert or update key-value pairs
method put(key, value):
if key exists in self.cache:                # Check if the key is already in the cache
remove key from self.key_order          # Remove key from its current position
elif length of self.cache equals self.capacity:  # If cache size has reached capacity
LRU_key = remove the first item from self.key_order  # Identify and remove the oldest key
delete LRU_key from self.cache          # Remove LRU key from the cache

insert (key, value) into self.cache         # Insert the new key-value pair
append key to the end of self.key_order     # Place the key at the end to mark it as recently used

Step-by-Step Explanation:

Initialization (LRUCache with capacity) :

You initialize your cache with a given capacity. An empty dictionary (
self.cache

) to hold the key-value pairs for O(1) access and an empty list (
self.key_order

) to track the order of access.

Get Method (
get(key)

) :

Check Existence : Use the dictionary to quickly check if the key exists.
Update Order : If the key exists, to mark it as recently used, you remove it from its current position in
self.key_order

and append it to the end.
Return Value : Return the value from the dictionary. If the key does not exist, return -1.

Put Method (
put(key, value)

) :

Check Existence : If the key exists already, update its position to the end of the order list and update its value in the dictionary.
Capacity Management : If adding this new key-value pair would exceed the cache’s capacity:

Remove the least recently used item (the first item in
self.key_order

).
Delete this item from the dictionary.

Insert New Value : Add the new key-value pair to the dictionary and mark it as recently used by appending it to the end of
self.key_order

.

Following this strategy ensures that both the

get

and

put

operations run in O(1) average time complexity, adhering to the constraints of the problem.