LRU Cache
LRU Cache
Design and simulate a Least Recently Used (LRU) cache with a given capacity. Implement two operations: - GET key: return the value if the key exists (and mark it as recently used), otherwise return -1 - PUT key value: insert or update the key-value pair. If the cache is at capacity, evict the least recently used key before inserting. Input format: - First line: two integers capacity and number of operations q - Next q lines: each line is either "GET key" or "PUT key value" Output: for each GET operation, print its result on a separate line.
Approach
Combine a hash map (key → node) with a doubly-linked list (most recent at head, LRU at tail). GET: move node to head, return value. PUT: if key exists update+move to head; if new, add at head and evict tail if over capacity.
Input
Output
- •
1 ≤ capacity ≤ 3000, 0 ≤ key, value ≤ 10^4
More System Design problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards