Design and implement a data structure for
Least Recently Used (LRU/eldest) cache. It should support the following operations:
get and
set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not
already present.
When the cache reached its capacity, it should
invalidate the least recently used (eldest) item before inserting a new item.
First version, time limit exceeded.
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
36
37
38
| public class LRUCache {
Map<Integer,Integer> cache = new HashMap<Integer,Integer>();
LinkedList<Integer> dll = new LinkedList<Integer>();
int cap = 0;
public LRUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
if(cache.containsKey(key)){
touch(key);
return cache.get(key);
}
else
return -1;
}
public void set(int key, int value) {
touch(key);
cache.put(key,value);
}
private void touch(int key){
int ind = dll.indexOf(key);//just do it once
if(ind==-1){
//need to insert to header, but need to check capacity before doing it
if(dll.size()==cap){
int k = dll.removeLast();
cache.remove(k);
}
dll.addFirst(key);
}else{
//if it contains the key, remove it and add it back to head
dll.remove(ind);
dll.addFirst(key);
}
}
}
|
Better solution that extends linked hash map, which keeps input sequence, and is able to remove eldest element.
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
| private Map<Integer, Integer> map;
public LRUCache(int capacity) {
map = new LinkedCappedHashMap<>(capacity);
}
public int get(int key) {
if(!map.containsKey(key)) { return -1; }
return map.get(key);
}
public void set(int key, int value) {
map.put(key,value);
}
private static class LinkedCappedHashMap<K,V> extends LinkedHashMap<K,V> {
int maximumCapacity;
LinkedCappedHashMap(int maximumCapacity) {
super(16, 0.75f, true);
this.maximumCapacity = maximumCapacity;
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maximumCapacity;
}
}
}
|
No comments:
Post a Comment