Design a least-recently-used cache

Design and implement a least-recently-used (LRU) cache with a fixed capacity. Support get(key) -> value and put(key, value) in average O( 1) time. When the cache is full, evict the least recently used entry. Explain your choice of data structures, detail how you update recency on reads and writes, and describe how you handle updates to existing keys, missing keys, and capacity edge cases (e.g., capacity = 0). Analyze time and space complexity.