DSA: Design an LRU Cache

Design a cache with get(key) and put(key, value) both O(1), evicting the least-recently-used entry when full.

Technical Reference & Key Concepts

The Challenge: LRU Cache

Implement an LRU cache supporting get and put in O(1), capacity fixed. Explain the data structure choice and why simpler options fail.

Core questions to address:

  1. Why can't a HashMap alone (or a Queue alone) implement LRU?
  2. What combination of structures achieves O(1) for both operations, and what's the exact role of each?
  3. What are the tricky implementation details (updating recency on get, eviction on full)?