Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

82. LRU Cache

MediumDay 24 of 60Linked List

Design an LRUCache class: a key value cache with a fixed capacity that evicts the least recently used key when it is full. LRUCache(capacity) creates it, get(key) returns the value or -1 if the key is missing, and put(key, value) inserts or updates the key. Reading or writing a key makes it the most recently used. If a put adds a new key beyond capacity, remove the least recently used key first. Both get and put must run in O(1) average time.

Example 1
Input: ops = ["LRUCache","put","put","get","put","get","put","get","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]
get(1) makes key 1 recent, so put(3,3) evicts key 2. Then put(4,4) evicts key 1.
Constraints
  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls to get and put
Hints
Frequently asked at: Amazon, Microsoft, Meta, Google, Goldman Sachs, Flipkart, Swiggy
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for ₹200/ 30 min