18. LRU Cache - Browser Cache Manager

You're building a browser cache system that stores frequently accessed resources (images, API responses, etc.). To manage memory efficiently, you need to implement a Least Recently Used (LRU) cache that automatically evicts the least recently used item when the cache reaches its capacity limit.

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support the following operations:

• get(key): Return the value of the key if it exists, otherwise return -1
• put(key, value): Insert or update the value. If the cache exceeds its capacity, evict the least recently used item

Requirements

1. Basic Operations

• get(key): Get value by key, return -1 if not found
• put(key, value): Insert or update key-value pair
• Both operations should be O(1) time complexity

2. Capacity Management

• Cache has a maximum capacity
• When capacity is exceeded, remove the least recently used item
• Both get and put operations count as "using" an item

Real-World Context

This problem models real browser caching systems where:

• Browser cache: Stores images, CSS, JS files with size limits
• API response caching: Caches API responses to reduce server load
• Image caching: Manages memory for frequently viewed images
• CDN caching: Content delivery networks use LRU for cache eviction