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.
Part 1: Implement an LRU Cache
Write a function that simulates an LRU (Least Recently Used) cache with a fixed positive capacity. The function receives the cache capacity and a list of operations. Each operation is either ('put', key, value) or ('get', key). A successful get makes that key the most recently used item. A put inserts or updates a key-value pair; if the cache grows beyond capacity, evict the least recently used key. Return a list containing the result of every operation: use None for put operations and the integer result for get operations. Your approach should support O(1) average-time get and put operations.
Constraints
- 1 <= capacity <= 100000
- 1 <= len(operations) <= 200000
- -10^9 <= key, value <= 10^9
- Average time complexity for both get and put should be O(1)
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: [None, None, 1, None, -1, None, -1, 3, 4]
Explanation: After get(1), key 1 becomes most recent. Putting key 3 evicts key 2. Putting key 4 later evicts key 1.