LRU Cache Implementation

Problem Description

Design and implement an LRU (Least Recently Used) cache. Your cache should support the following operations:

get(key) - Gets the value (will always be positive) of the key if the key exists in the cache, otherwise returns -1.
put(key, value) - Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. For the purpose of this question, when a new key is inserted, regard it as most recently used.

The cache is initialized with a positive capacity.

Example:

LRUCache cache = new LRUCache(2); // capacity is 2

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Follow up:

Could you do both operations in O(1) time complexity?

Naive Solution

A naive solution could use a simple array or list to store the key-value pairs along with a timestamp indicating the last time each key was accessed. The get and put operations would involve iterating through the array/list to find the key. When the cache is full, we would iterate through the array/list to find the least recently used item (smallest timestamp) and remove it.

This approach is easy to implement but has a time complexity of O(n) for both get and put operations, where n is the capacity of the cache, because you potentially have to scan the entire array to find the least recently used item.

Optimal Solution

To achieve O(1) time complexity for both get and put operations, we can use a combination of a doubly linked list and a hash map.

Doubly Linked List: The doubly linked list will store the key-value pairs in the order of their use. The most recently used item will be at the head of the list, and the least recently used item will be at the tail.
Hash Map: The hash map will store the key-value pairs, where the key is the key and the value is a pointer (reference) to the corresponding node in the doubly linked list. This allows us to quickly access any node in the linked list in O(1) time.

Here's how the get and put operations work:

get(key):
1. Check if the key exists in the hash map.
2. If the key does not exist, return -1.
3. If the key exists, get the corresponding node from the hash map.
4. Move the node to the head of the doubly linked list (mark it as most recently used).
5. Return the value of the node.
put(key, value):
1. Check if the key exists in the hash map.
2. If the key exists, update the value of the corresponding node in the linked list.
3. Move the node to the head of the doubly linked list (mark it as most recently used).
4. If the key does not exist:
  - Create a new node with the given key and value.
  - Add the new node to the head of the doubly linked list.
  - Add the key-node pair to the hash map.
  - If the cache is full (size exceeds capacity):
    - Remove the tail node from the doubly linked list (least recently used item).
    - Remove the corresponding key from the hash map.

Code Implementation (Python)

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = None
        self.tail = None
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            self.size += 1

            if self.size > self.capacity:
                self._remove_tail()

    def _add_to_head(self, node):
        if not self.head:
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    def _remove_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_tail(self):
        if self.tail:
            del self.cache[self.tail.key]
            self._remove_node(self.tail)
            self.size -= 1


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Big(O) Runtime Analysis

get(key): O(1) - The hash map allows us to find the node in O(1) time. Moving the node to the head of the linked list also takes O(1) time.
put(key, value): O(1) - The hash map allows us to find the node (if it exists) in O(1) time. Adding a new node to the head of the linked list or updating an existing node also takes O(1) time. Removing the tail node (if the cache is full) also takes O(1) time.

Big(O) Space Usage Analysis

The space complexity is O(capacity), where capacity is the maximum number of key-value pairs that the cache can store. This is because we store each key-value pair in both the hash map and the doubly linked list. In the worst-case scenario, the cache will be full, so the space usage will be proportional to the capacity.

Edge Cases

Cache with zero capacity: If the capacity is zero, any put operation should not store any key-value pairs, and all get operations should return -1.
Inserting an existing key with a new value: The put operation should update the value of the existing key and move the node to the head of the list, marking it as the most recently used item.
Getting a non-existing key: The get operation should return -1.
Cache is full: When putting a new key-value pair into a full cache, the least recently used item should be evicted.
Putting the same key multiple times consecutively: It should still work correctly.

Design and implement an LRU cache with O(1) `get` and `put` operations.