How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Implement Cache and Rotate Matrix | Amazon Coding Question

Quick Overview

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.

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.

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

Expected 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.

Input: (1, [('put', 1, 1), ('get', 1), ('put', 2, 2), ('get', 1), ('get', 2)])

Expected Output: [None, 1, None, -1, 2]

Explanation: With capacity 1, inserting key 2 evicts key 1 immediately.

Input: (2, [('get', 5)])

Expected Output: [-1]

Explanation: Edge case: getting a missing key from an empty cache returns -1.

Hints

A hash map gives fast access to nodes by key, but you still need a way to update recency quickly.
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

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

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

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

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

Expected 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.

Input: ([[42]],)

Expected Output: [[42]]

Explanation: Edge case: a 1x1 matrix stays the same after rotation.

Input: ([],)

Expected Output: []

Explanation: Edge case: an empty matrix should be returned unchanged.

Hints

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

Quick Overview