Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

LRU Cache

Hash Mapshard

Course · Section 9: Data Structures, Modern Operators and Strings · Lecture 124: Maps: Fundamentals

Design a Least-Recently-Used (LRU) cache with a fixed capacity. Implement `LRUCache`: - `new LRUCache(capacity)` creates a cache of the given capacity. - `get(key)` returns the value, or `-1` if absent; using a key counts as a use. - `put(key, value)` inserts or updates; if over capacity, evict the least recently used key.

Examples

Input: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)
Output: [1, -1, -1, 3, 4]
put(3,3) evicts key 2; put(4,4) evicts key 1.

Sample tests

Input: capacity 2 eviction scenario
Output: [1,-1,-1,3,4]
Input: update keeps key fresh
Output: [-1,10]

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Forgetting that get also counts as a use and must refresh recency.
  • Evicting the newest instead of the oldest key.

Learning resources

  • Wikipedia: Cache replacement (LRU)
Approach & explanation (try first)

A Map keeps keys in insertion order, so re-inserting on access marks recency and the first key is always the least recently used. All operations are O(1) average. O(capacity) space.

Loading...
⌘/Ctrl + Enter

Run your code to see results.