Explanation:

An LRU (Least Recently Used) cache is a data structure that stores a limited number of items and automatically removes the least recently used item when the cache exceeds its capacity. This is particularly useful in scenarios where you want to manage memory efficiently while ensuring quick access to frequently accessed data. In a typical LRU cache implementation, we aim to achieve O(1) time complexity for both lookups and insertions.

Key Talking Points:

• Objective: Store limited items and evict the least recently used item when capacity is exceeded.
• Operations: Support constant time complexity O(1) for both get and put operations.
• Data Structures: Typically implemented using a combination of a doubly linked list and a hash map.

Pseudocode:

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)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add(self, node: Node):
        prev = self.tail.prev
        prev.next = node
        self.tail.prev = node
        node.prev = prev
        node.next = self.tail

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

    def put(self, key: int, value: int):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

Follow-Up Questions and Answers:

• Q: What if the cache capacity is set to zero?

  • Answer: If the capacity is zero, the cache cannot store any items. All put operations will essentially become no-ops, and all get operations will return -1, indicating a cache miss.

• Q: How would you handle concurrency in an LRU cache?

  • Answer: To handle concurrency, you might use locks to synchronize access to the cache. Consider using reader-writer locks if the cache is read-heavy, or employ concurrent data structures if available in your programming language.

• Q: What are some alternative cache eviction policies?

  • Answer: Besides LRU, other policies include Least Frequently Used (LFU), Most Recently Used (MRU), and Random Replacement, each with different use cases and trade-offs.

• Q: Can you explain the trade-offs between time complexity and space complexity in an LRU cache?

  • Answer: An LRU cache achieves O(1) time complexity for operations by using additional space for the hash map and doubly linked list pointers. This is a trade-off between time and space complexity, as we use extra memory to optimize for speed.

CHAPTER: Databases