LRU Cache – Complete Tutorial Hard 0 attempts
GeeksforGeeks ↗

LRU Cache – Complete Tutorial

Hard Stack&Queue GeeksforGeeks

Build a data structure that implements a Least Recently Used (LRU) cache. It needs two operations: get(key), which returns the stored value for that key or -1 if the key isn't present, and put(key, value), which adds a new key-value pair or updates an existing one. Once the cache is full, inserting a fresh key must first evict whichever entry was used least recently. Both get and put are expected to run in constant, O(1) time.

Input Format
Implement the factory function lruCacheCompleteTutorial. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = [2]
operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]
Output
[null,null,1,null,-1,null,-1,3,4]

Example 2

Input
constructorArgs = [1]
operations = [["put",1,1],["put",1,2],["get",1],["put",2,3],["get",1],["get",2]]
Output
[null,null,2,null,-1,3]
Constraints
  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls
Test Cases (2)
Case 1
Args: [[2],[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]] Expected: [null,null,1,null,-1,null,-1,3,4]
Case 2
Args: [[1],[["put",1,1],["put",1,2],["get",1],["put",2,3],["get",1],["get",2]]] Expected: [null,null,2,null,-1,3]
Topics
Stack&Queue

Approach: HashMap + Ordered Map

Use a Map which maintains insertion order in JavaScript. On get/put, delete and re-insert the key to move it to the end (most recent). On capacity overflow, delete the first key (least recent).

javascript
function lruCacheCompleteTutorial(capacity) {
  const cache = new Map();
  return {
    get(key) {
      if (!cache.has(key)) return -1;
      const val = cache.get(key);
      cache.delete(key);
      cache.set(key, val);
      return val;
    },
    put(key, value) {
      cache.delete(key);
      cache.set(key, value);
      if (cache.size > capacity) cache.delete(cache.keys().next().value);
    }
  };
}

Time Complexity: O(1) per operation

Space Complexity: O(capacity)

Saved in this browser only. Private to you.

JavaScript