-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLRU_Cache.java
More file actions
35 lines (22 loc) · 1.25 KB
/
LRU_Cache.java
File metadata and controls
35 lines (22 loc) · 1.25 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
* https://docs.google.com/document/d/1TSJ_2f9KfyPdkUp9MwHbfIks8bihj5rmMhc2y-rxzKM/edit?tab=t.0#heading=h.wsyef8ev9na0
* LRU Cache Implementation - Room 5
Design and implement a Least Recently Used (LRU) cache. The cache should support the following operations in O(1) time complexity:
get(int key): Returns the value associated with the key if it exists, otherwise return -1.
put(int key, int value): Insert or update the key-value pair. If the cache reaches its capacity, remove the least recently used item before inserting a new one.
The cache follows the Least Recently Used (LRU) policy, meaning the least recently accessed element is removed when the cache is full.
Example Usage:
LRUCache cache(2); // Capacity = 2
cache.put(1, 10);
cache.put(2, 20);
cout << cache.get(1) << endl; // Output: 10 (1 is now most recently used)
cache.put(3, 30); // Removes key 2 (Least Recently Used), because capacity is of size 2
cout << cache.get(2) << endl; // Output: -1 (Key 2 was evicted)
cout << cache.get(3) << endl; // Output: 30
Keywords/Hints:
doubly linked list
hash map
On a get(), the searched element becomes the most recently used one.
On a put(), inserted element is the most recent one used.
Don’t forget to take into consideration the cache capacity
*/