Implement an LRU cache
Company: Disney
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## LRU Cache
Design and implement a fixed-capacity **Least Recently Used (LRU)** cache.
### Operations
- `get(key) -> value | -1/null`: Return the value if present; otherwise indicate missing. Accessing a key makes it **most recently used**.
- `put(key, value)`: Insert or update the value. Updating also makes it **most recently used**.
### Eviction rule
- When inserting causes the cache to exceed capacity, evict the **least recently used** item.
### Requirements
- Target time complexity: `O(1)` average for both `get` and `put`.
### Input/Output format
You may choose an interface/class-based implementation (common in interviews). Clearly define how missing keys are represented (e.g., `-1` for integers).
Quick Answer: This question evaluates understanding of data structures and algorithmic optimization for constant-time cache operations, with emphasis on cache eviction policies and state management.
Implement solution(capacity, operations). operations contains ["put", key, value] and ["get", key]. Return the values produced by get operations, using -1 for missing keys. get and put must update recency; inserting beyond capacity evicts the least recently used key.
Constraints
- 0 <= capacity <= 10^5
- operations length <= 2 * 10^5
- keys and values are integers
Examples
Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]])
Expected Output: [1, -1, -1, 3, 4]
Input: (1, [['put', 5, 10], ['put', 5, 11], ['get', 5], ['put', 6, 12], ['get', 5], ['get', 6]])
Expected Output: [11, -1, 12]
Input: (0, [['put', 1, 1], ['get', 1]])
Expected Output: [-1]
Hints
- Use a hash map plus a recency order structure.
- Updating an existing key also makes it most recently used.