Skip to content
Onsite
11 / 20

LRU Cache

MediumP1Coding

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy.

Implement the LRUCache class:

  • LRUCache(capacity) creates the cache with a positive capacity.
  • get(key) returns the value of key if it exists, otherwise -1.
  • put(key, value) updates the value of key if it exists, otherwise adds the pair. If the number of keys then exceeds capacity, evict the least recently used key.

Both get and put must run in O(1) average time. A successful get and any put count as a use of that key.

Example 1

Input
["LRUCache","put","put","get","put","get","put","get","get","get"] [[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]
Why
get(1) makes key 1 recent, so put(3,3) evicts key 2. put(4,4) then 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

Run checks the 2 visible tests, Submit all 5.