Implement Cache and Rotate Matrix

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:

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

Output:

[[7, 4, 1],
 [8, 5, 2],
 [9, 6, 3]]

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

Example 1

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])
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.

Example 2

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])
Output: [None, None, None, None, 10, -1, 3]

Explanation: Updating key 1 changes its value and makes it most recent, so key 2 is evicted when key 3 is inserted.

Hints

1. A hash map gives fast access to nodes by key, but you still need a way to update recency quickly.
2. A doubly linked list with dummy head/tail nodes makes removal and insertion of recently used items easier.

Part 2: Rotate a Square Matrix

Given an n x n integer matrix, rotate it 90 degrees clockwise in place. You may not allocate another n x n matrix. For easier testing, return the same matrix after modifying it. If the matrix is empty, return an empty list.

Constraints

• 0 <= n <= 200
• matrix is square: len(matrix[i]) == n for all valid i
• -10^9 <= matrix[i][j] <= 10^9
• Do not allocate another n x n matrix

Examples

Example 1

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Explanation: This is the standard 3x3 clockwise rotation example.

Example 2

Input: ([[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]],)
Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Explanation: A 4x4 example showing the same in-place transformation on a larger matrix.

Hints

1. A clockwise rotation can be broken into two in-place steps: transpose the matrix, then reverse each row.
2. If you transpose in place, only swap entries above the main diagonal to avoid undoing work.