Lv.2designhashlinked-list
LRU Cache Simulation
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| capacity | ops | result |
|---|---|---|
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
-
capacity,ops.length [1, key, value]or[2, key, 0]withkey,value
Expected complexity
- Time
- O(Q)
- Space
- O(capacity)
Examples
| capacity | ops | Expected |
|---|---|---|
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 (LinkedHashMap with access order, OrderedDict, or std::list + splice). Scanning an array per command is
.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 214 ms | estimated |
| C++ (GCC, gnu++23) | 214 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1900 ms | derived |
| Kotlin 2.4 (JVM) | 1428 ms | estimated |
| C# 14 (.NET 10) | 1428 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 7 | verdict only |
| performance | 60 | 4 | verdict only |