Skip to content
RED SAGSkills
medium30 ptshash-maplinked-listdesign

Replay an LRU Cache

Simulate a least-recently-used cache with room for capacity entries. You are given a list of operations ops:

["put", key, value] stores the value, or updates it if the key exists. Either way the key becomes the most recently used. If a new key would exceed capacity, first evict the least recently used key.

["get", key] returns the stored value and marks the key as most recently used, or returns -1 if the key is not in the cache.

Return an array with the result of every get, in order.

Example 1

Input: capacity = 2, ops = [["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]

Example 2

Input: capacity = 1, ops = [["put",1,1],["put",2,2],["get",1],["get",2]]
Output: [-1,2]

Constraints

  • 1 <= capacity <= 3000
  • 0 <= ops.length <= 10^5
  • Keys and values are numbers or strings.
Hint 1

A JavaScript Map remembers insertion order, so its first key is the oldest.

Hint 2

To mark a key as recently used, delete it and insert it again.

Good practice for: Backend Developer, Full Stack Developer, Frontend Developer, Mobile App Developer, Cloud Engineer, Database Administrator

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.