Problem: Design a Least Recently Used (LRU) Cache

Design and implement a Least Recently Used (LRU) cache with a fixed capacity.

Core Requirements

• Operations: Support get(key) which returns the value associated with the key, and put(key, value) which inserts or updates a key-value pair.
• Performance: Both get and put operations must achieve an average time complexity of O(1).
• Eviction Policy: When the cache reaches its fixed capacity and a new item is added, the least recently used entry must be evicted.

Design Considerations

• Data Structures: Explain your choice of underlying data structures.
• Recency Updates: Detail how recency is updated on both read (get) and write (put) operations.
• Edge Cases: Describe how you handle:
  • Updates to existing keys.
  • Requests for missing keys (get).
  • Capacity edge cases (e.g., capacity = 0 or 1).

Analysis

• Complexity: Analyze the time and space complexity of your solution.