Implement LRU Cache with without recursion

Question

Implement a Trie data structure that supports push, pop, and peek operations in O(1) time.

Codemia · Accepted Answer

To implement an LRU (Least Recently Used) Cache, we need a data structure that allows us to efficiently store key-value pairs and maintain the order of access. The key operations required are:

1. **Get(key)**: Retrieve the value associated with the key, and mark it as recently used.
2. **Put(key, value)**: Insert or update the value of the key and mark it as recently used. If the cache exceeds its capacity, remove the least recently used item.

The optimal approach for this problem leverages a combination of a Hash Map and a Doubly Linked List. The Hash Map provides O(1) access to key-value pairs, while the Doubly Linked List maintains the order of usage, allowing us to remove the least recently used item efficiently.

Here’s the step-by-step algorithm:

1. **Initialization**: Initialize the capacity of the cache and set up a Hash Map to store key-value pairs. Additionally, create a Doubly Linked List to keep track of the order of usage.
2. **Get Operation**:
   - Check if the key exists in the Hash Map.
   - If it exists, move the corresponding node in the linked list to the front (mark it as most recently used) and return the value.
   - If it does not exist, return -1.
3. **Put Operation**:
   - Check if the key already exists:
     - If it does, update the value and move the node to the front of the list.
   - If it does not exist:
     - If the cache is at capacity, remove the tail node from the linked list (which is the least recently used) and delete its entry from the Hash Map.
     - Insert the new key-value pair at the front of the linked list and add it to the Hash Map.

Here is the Python implementation of the LRU Cache:

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)  # Dummy head
        self.tail = Node(0, 0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

def _remove(self, node):
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev

def _add_to_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_front(node)
            return node.value
        return -1

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            node.value = value
            self._add_to_front(node)
        else:
            if len(self.cache) == self.capacity:
                lru_node = self.tail.prev
                self._remove(lru_node)
                del self.cache[lru_node.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_front(new_node)
```
This code defines a `Node` class for the doubly linked list and an `LRUCache` class that implements the required methods.

The time complexity for both `get` and `put` operations is O(1), thanks to the Hash Map for direct access and the doubly linked list for efficient insertion and removal. The space complexity is O(n), where n is the capacity of the cache, as we need to store each key-value pair in the Hash Map and each corresponding node in the linked list.

1. **Capacity of 0**: If the capacity is set to 0, any `put` operation should not store any items, and `get` should always return -1.
   - Example: `cache = LRUCache(0); cache.put(1, 1); cache.get(1)` should return -1.

2. **Repeated `put` operations**: If a key is put multiple times, it should update the value without adding duplicates.
   - Example: `cache = LRUCache(2); cache.put(1, 1); cache.put(1, 10); cache.get(1)` should return 10.

3. **Accessing non-existent keys**: When trying to get a key that was never set, it should return -1.
   - Example: `cache.get(2)` should return -1 if it was never added.

Implement LRU Cache with without recursion

Compass

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Compass Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string