Katkat
Back

Implement Cache and Rotate Matrix

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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]]