LRU Cache

Medium~20 min

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(capacity) — Initialize the LRU cache with positive size capacity.
  • get(key) — Return the value of the key if it exists, otherwise return -1. This also marks the key as recently used.
  • put(key, value) — Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.

Examples

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]
Explanation: LRUCache cache = new LRUCache(2); cache.put(1, 1); // cache is {1=1} cache.put(2, 2); // cache is {1=1, 2=2} cache.get(1); // return 1 cache.put(3, 3); // evicts key 2, cache is {1=1, 3=3} cache.get(2); // return -1 (not found) cache.put(4, 4); // evicts key 1, cache is {3=3, 4=4} cache.get(1); // return -1 (not found) cache.get(3); // return 3 cache.get(4); // return 4

Constraints

  • 1 <= capacity <= 100
  • 0 <= key <= 1000
  • 0 <= value <= 10000
  • At most 1000 calls will be made to get and put
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run