Funcia
Lv.2designhashlinked-list

LRU Cache Simulation

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Simulate an LRU cache of size capacity. [1, key, value] stores (updating an existing key, or evicting the least recently used key first when full); [2, key, 0] appends the value or -1. Stores and successful lookups mark the key as most recently used. Return the lookup results in order.

Examples

capacityopsresult
2[[1, 1, 10], [1, 2, 20], [2, 1, 0], [1, 3, 30], [2, 2, 0], [2, 3, 0], [2, 1, 0]][10, -1, 30, 10]
1[[1, 5, 1], [1, 5, 2], [2, 5, 0], [1, 6, 3], [2, 5, 0]][2, -1]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(capacity: int, ops: int[][]) → int[]

Constraints

  • 1≤1 \le capacity ≤100,000\le 100{,}000, 1≤1 \le ops.length ≤200,000\le 200{,}000
  • [1, key, value] or [2, key, 0] with 0≤0 \le key, value ≤109\le 10^9

Expected complexity

Time
O(Q)
Space
O(capacity)

Examples

capacityopsExpected
2[[1,1,10],[1,2,20],[2,1,0],[1,3,30],[2,2,0],[2,3,0],[2,1,0]][10,-1,30,10]
1[[1,5,1],[1,5,2],[2,5,0],[1,6,3],[2,5,0]][2,-1]

Hint

Hint

Hash map from key to a node of a doubly linked list ordered by recency: move a used node to the front, evict from the back, all O(1)O(1) (LinkedHashMap with access order, OrderedDict, or std::list + splice). Scanning an array per command is O(capacity)O(\text{capacity}).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)214 msestimated
C++ (GCC, gnu++23)214 msderived
Python 3.131000 msderived
Java 251900 msderived
Kotlin 2.4 (JVM)1428 msestimated
C# 14 (.NET 10)1428 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness407verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.