codejump
HardPro challengePythonJavaScriptTypeScript

LRU Cache

DataStructuresPatternsObjects

Design a cache with fixed capacity that evicts the least-recently-used
entry when full. Both get and put should run in amortised O(1).

API

  • get(key) → returns the value if present and marks the key as most

recently used; otherwise returns -1.

  • put(key, value) → inserts or updates. If the cache is full and the key

is new, evict the least-recently-used entry first.

solve(capacity, ops) replays a list of operations and returns one entry per
op (null for puts, the gotten value or -1 for gets).

Sample tests

Test #1Classic LeetCode example
Input: [2,[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]]]
Output: [null,null,1,null,-1]
Test #2Updating an existing key refreshes its recency
Input: [2,[["put",1,1],["put",2,2],["put",1,10],["get",1],["get",2]]]
Output: [null,null,null,10,2]
Test #3Capacity 1 evicts on every new put
Input: [1,[["put",1,"a"],["put",2,"b"],["get",1],["get",2]]]
Output: [null,null,-1,"b"]
Test #4get(1) saves it; (2) becomes LRU and is evicted
Input: [3,[["put",1,1],["put",2,2],["put",3,3],["get",1],["put",4,4],["get",2]]]
Output: [null,null,null,1,null,-1]
Test #5Missing key returns -1
Input: [2,[["get",99]]]
Output: [-1]
← All challenges