medium

LRU Cache

Design a cache with a fixed capacity supporting get(key) and put(key, value) in constant time. When inserting into a full cache, evict the entry that was accessed least recently (both gets and puts count as access).

Constraints
  • 1 ≤ capacity ≤ 3000
  • 0 ≤ key, value ≤ 10^5
  • At most 2 · 10^5 operations
Examples
in: capacity = 2; put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)
out: 1, -1, -1, 3, 4

Code it yourself

Solve in
Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.
Hints:
Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.