Implement an LRU cache
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement an in-memory cache that evicts entries using the **Least Recently Used (LRU)** policy.
The cache should store key–value pairs and support the following operations:
- `LRUCache(int capacity)`: Initialize the cache with a positive integer `capacity` representing the maximum number of key–value pairs it can hold.
- `int get(int key)`:
- If the key exists in the cache, return its value and mark this key as **most recently used**.
- If the key does not exist, return `-1`.
- `void put(int key, int value)`:
- Insert or update the value of the given key.
- When inserting a new key causes the number of items to exceed `capacity`, you must **evict exactly one key–value pair: the one that has been least recently used** (i.e., the one whose `get` or `put` was accessed furthest in the past).
- Updating an existing key should also mark it as **most recently used**.
**Requirements:**
- All `get` and `put` operations must run in **O(1)** average time.
- You may assume:
- Keys and values are integers.
- `capacity >= 1`.
Describe the data structures you would use and then implement the LRU cache in a language of your choice.
Quick Answer: This question evaluates a candidate's ability to design and implement efficient data structures that meet strict O(1) time constraints while managing access-based eviction policies, testing competencies in algorithmic reasoning, state management, and performance trade-offs.