Embedding Cache (LRU)
An inference service caches recently computed text embeddings to avoid recomputing them. The cache holds a fixed number of entries; when it fills, the least-recently-used embedding is evicted. Implement the cache with O(1) get and put. (The DSA here is a hash map plus a doubly linked list — the embeddings are just the payload.)
Problem
Implement an LRUCache with capacity C supporting get(key) → value or -1, and put(key, value). Both must run in O(1) average time. Accessing or inserting a key marks it most-recently-used; inserting beyond capacity evicts the least-recently-used key.
Input
A capacity C (1 ≤ C ≤ 10^5) and a sequence of get/put operations with integer keys and values.
Output
For each get, the stored value or -1 if absent.
Constraints
- 1 ≤ C ≤ 100,000
- Keys and values are integers
- get and put must be O(1) average
Examples
Example 1
Input
C=2; put(1,10); put(2,20); get(1)→; put(3,30); get(2)→
Output
10, then -1
get(1) returns 10 and marks 1 as recent; put(3,30) evicts the LRU key 2; get(2) is now -1.
Example 2
Input
C=1; put(5,50); put(6,60); get(5)→
Output
-1
Capacity 1: put(6) evicts key 5, so get(5) returns -1.