LRU Cache - Python Solution

1. Introduction

The Least Recently Used (LRU) Cache is a popular data structure problem that demonstrates the use of hash tables and double-ended queues (deque) to efficiently manage a cache with a fixed size. The challenge is to design a cache that evicts the least recently used item when it reaches its capacity, while providing constant time operations for adding and retrieving items.

Problem

Implement the LRUCache class:

- LRUCache(int capacity) initializes the LRU cache with positive size capacity.

- int get(int key) returns the value of the key if it exists, otherwise returns -1.

- void put(int key, int value) updates the value of the key if it exists, or adds the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.

Both get and put operations must run in O(1) average time complexity.

2. Solution Steps

1. Use a hash table to store key-value pairs for O(1) access.

2. Use a double-ended queue (deque) to keep track of the order of usage of keys.

3. For put operations, add or update key-value pairs in the hash table. Move the key to the end of the deque to mark it as recently used.

4. If adding a new key exceeds the cache capacity, remove the least recently used key from the front of the deque and its corresponding entry from the hash table.

5. For get operations, return the value from the hash table if the key exists. Move the key to the end of the deque to mark it as recently used.

6. If the key does not exist, return -1.

3. Code Program

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# Example Usage
lRUCache = LRUCache(2)
lRUCache.put(1, 1)  # cache is {1=1}
lRUCache.put(2, 2)  # cache is {1=1, 2=2}
print(lRUCache.get(1))    # return 1
lRUCache.put(3, 3)  # LRU key was 2, evicts key 2, cache is {1=1, 3=3}
print(lRUCache.get(2))    # returns -1 (not found)
lRUCache.put(4, 4)  # LRU key was 1, evicts key 1, cache is {4=4, 3=3}
print(lRUCache.get(1))    # return -1 (not found)
print(lRUCache.get(3))    # return 3
print(lRUCache.get(4))    # return 4

Output:

1
-1
-1
3
4

Explanation:

1. LRUCache Class: The LRUCache class uses an OrderedDict to maintain the insertion order of keys for efficient LRU operations.

2. Cache Initialization: The cache is initialized with a given capacity.

3. Get Operation: The get method retrieves an item and moves it to the end of the OrderedDict to mark it as recently used.

4. Put Operation: The put method updates or adds items to the cache, moving them to the end of the OrderedDict. It also evicts the least recently used item if the capacity is exceeded.

5. Efficient Access: The OrderedDict allows for O(1) access and update operations, satisfying the time complexity requirements.

6. Eviction Logic: The least recently used item is evicted from the cache when the capacity is exceeded to maintain the cache size.