LRU Cache

LRU Cache

Design a fixed-capacity cache that evicts the least-recently-used entry — the single most-asked machine-coding warm-up.

Requirements

• Capacity is fixed at construction; the cache never holds more than capacity entries.
• Recency: both get (hit) and put (insert or update) make a key the most-recently-used.
• Eviction: inserting a new key into a full cache evicts the least-recently-used key. Updating an existing key never evicts.
• A get miss changes nothing.
• Target O(1) average time per operation — an ordered map / hash map + doubly linked list.

API to implement

Implement the class LRUCache. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | put <key> <value> | — | Insert or update key with value. Both count as a use. If inserting a new key exceeds capacity, evict the least-recently-used entry first. | | get <key> | int | Return the value for key, or -1 if absent. A successful get counts as a use. |

Input format

The first line contains Q, the number of operations. The second line contains the constructor argument: capacity — the maximum number of entries the cache holds (≥ 1). Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

9
2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
-1
-1
3
4

5
1
put 5 50
get 5
put 6 60
get 5
get 6

50
-1
60