LRU Cache for Query Results
MediumAsked in:Amazon•Stage:Phone Screen
designhash_tablelinked_listsimulation
Problem Statement
Design a data structure that simulates an LRU (Least Recently Used) cache for query results. It must support retrieving a value by key and inserting/updating a key‑value pair while evicting the least recently accessed entry when the capacity is exceeded.
Input Format
The first line contains two integers n and capacity, the number of operations and the maximum size of the cache. The next n lines each describe an operation. An operation is either "GET key" to retrieve the value associated with key, or "PUT key value" to insert or update the key with the given value.
Output Format
For each GET operation output the value if the key exists in the cache; otherwise output -1. Each result should be printed on its own line in the order the GET operations appear.
Constraints
- 1 <= n <= 10^5
- 1 <= capacity <= 10^5
- 0 <= key, value <= 10^9
- The total number of PUT operations does not exceed n