https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) 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 item before inserting a new item.
class pair {
public int key;
public int value;
public pair(int k, int v) {
super();
this.key = k;
this.value = v;
}
public void setValue(int value) {
this.value = value;
}
}
class cmp implements Comparator {
public int compare(Object o1, Object o2) {
pair p1 = (pair) o1;
pair p2 = (pair) o2;
if(p1.key < p2.key) {
return -1;
} else if(p1.key == p2.key) {
if(p1.value == p2.value) {
return 0;
} else if(p1.value < p2.value) {
return -1;
} else {
return 1;
}
} else {
return 1;
}
}
}
public class LRUCache {
public Set<pair> stack = null;
public HashMap<Integer, Integer> mapping = null;
public TreeMap<Integer, Integer> timeToKey = null;
public TreeMap<Integer, Integer> keyToTime = null;
public int cap = 0;
public int counter = 0;
public LRUCache(int capacity) {
this.mapping = new HashMap<Integer, Integer> ();
this.timeToKey = new TreeMap<Integer, Integer> ();
this.keyToTime = new TreeMap<Integer, Integer> ();
this.cap = capacity;
this.counter = 0;
}
public int get(int key) {
if(!mapping.containsKey(key)) {
return -1;
} else {
counter++;
int value = mapping.get(key);
int time = keyToTime.get(key);
keyToTime.put(key, counter);
timeToKey.remove(time);
timeToKey.put(counter, key);
return value;
}
}
public void set(int key, int value) {
counter++;
if(mapping.containsKey(key)) {
int time = keyToTime.get(key);
keyToTime.put(key, counter);
timeToKey.remove(time);
timeToKey.put(counter, key);
mapping.put(key, value);
} else {
if(mapping.size() < cap) {
mapping.put(key, value);
keyToTime.put(key, counter);
timeToKey.put(counter, key);
} else {
int lru = timeToKey.pollFirstEntry().getValue();
mapping.remove(lru);
mapping.put(key, value);
keyToTime.put(key, counter);
timeToKey.put(counter, key);
}
}
}
}