Implement an LRU cache
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design and implement a data structure for a Least Recently Used (LRU) cache with a fixed capacity.
The cache must support:
- `get(key)`: return the value for `key` if present; otherwise return `-1`. This operation marks the key as most-recently-used.
- `put(key, value)`: insert or update the value for `key`. This operation marks the key as most-recently-used. If inserting causes the cache to exceed capacity, evict the least-recently-used key.
Constraints:
- Aim for average O(1) time per operation.
- Use standard in-memory data structures (no external databases).
Overview: This question evaluates understanding of data structures and algorithmic design for caching and eviction policies, focusing on achieving efficient operations under strict time-complexity constraints.