Implement a Least-Recently-Used Cache

Design and implement an in-memory least-recently-used cache.

Requirements:

• The cache is initialized with a positive integer capacity.
• Implement get(key): return the value associated with key if it exists; otherwise return -1 or null.
• Implement put(key, value): insert or update the value for key.
• Any successful get or put makes that key the most recently used item.
• If inserting a new key causes the cache to exceed capacity, evict the least recently used key.
• Both get and put should run in O(1) average time.

Explain your data structures, edge cases, and time/space complexity.

Implement a Least-Recently-Used Cache

Design and implement an in-memory Least-Recently-Used (LRU) cache.

Implement solution(capacity, operations).

• capacity is the maximum number of keys the cache can hold.
• Each operation is a list of 3 integers:
  • [1, key, 0] means get(key)
  • [2, key, value] means put(key, value)
• For every get, append the returned value to the answer list.
• If a key does not exist, get should return -1.
• Any successful get or any put makes that key the most recently used.
• If inserting a new key would exceed capacity, evict the least recently used key.

To achieve O(1) average time per operation, a correct solution should combine:

• a hash map from key to node, and
• a doubly linked list that stores keys from most recently used to least recently used.

Important edge cases to handle:

• empty operations
• capacity of 1
• updating an existing key should not increase cache size
• missing keys on get
• negative keys or values

Constraints

• 1 <= capacity <= 10^5
• 0 <= len(operations) <= 2 * 10^5
• Each operation has exactly 3 integers
• operation[0] is either 1 (get) or 2 (put)
• -10^9 <= key, value <= 10^9

Examples

Example 1

Input: (2, [[2, 1, 1], [2, 2, 2], [1, 1, 0], [2, 3, 3], [1, 2, 0], [2, 4, 4], [1, 1, 0], [1, 3, 0], [1, 4, 0]])
Output: [1, -1, -1, 3, 4]

Explanation: After get(1), key 1 becomes most recent, so key 2 is evicted when key 3 is inserted. Later key 1 is evicted when key 4 is inserted.

Example 2

Input: (1, [[2, 2, 1], [1, 2, 0], [2, 3, 2], [1, 2, 0], [1, 3, 0]])
Output: [1, -1, 2]

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

Hints

1. A hash map can find a key in O(1), but by itself it cannot tell you which key is least recently used.
2. Use a doubly linked list with dummy head and tail nodes so you can remove or move any cache entry in O(1).