Implement Cache and Rotate Matrix
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Solve the following two independent coding tasks.
### Task 1: Implement an LRU Cache
Design a data structure `LRUCache` that stores integer keys and integer values with a fixed positive capacity.
Implement:
- `LRUCache(int capacity)`: initializes the cache.
- `int get(int key)`: returns the value for `key` if it exists; otherwise returns `-1`. Accessing a key makes it the most recently used item.
- `void put(int key, int value)`: inserts or updates the key-value pair. If the cache exceeds capacity, evict the least recently used item.
Expected performance:
- `get` and `put` should run in `O(1)` average time.
Clarify your design, including how you track recency and how you handle updates and evictions.
### Task 2: Rotate a Square Matrix
Given an `n x n` integer matrix, rotate it 90 degrees clockwise in place.
Requirements:
- Modify the input matrix directly.
- Do not allocate another `n x n` matrix.
Example:
Input:
```text
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
```
Output:
```text
[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]
```
Quick Answer: This two-part question evaluates competency in data structure design and in-place array manipulation, specifically the ability to implement an LRU cache with O(1)-average operations (including recency management, updates, and evictions) and to rotate an n x n matrix 90 degrees clockwise in place without extra space.
