# LRU Cache

Hard

## Question

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.

Example
Input:

``````2, [set(2,1),set(1,1),get(2),set(4,1),get(1),get(2)]
``````

Expected output:

``````[1,-1,1]
``````

Challenge
Could you do both operations in O(1) time complexity?

## Thinking

• Using Map<Integer, Integer> to store key, value
• Using a list to store keys ordered by access time
• To keep the keys order by access, the key should be always moved to the last position (remove object from list and add object again)
• The least recently used always be the first element in the list.

## Review

• Using a deLinkedList and a map to do it. It takes O(1) to get key from map and also only O(1) to move the object form begin to new position.
• Using LinkedHashMap to do it. But it may not be interviewers want.
• LintCode is not support DeLinkedList
• Create an empty deLinkedList first. Then use general methods to do add, move, and pop. At first I didn’t create an empty deLinkedList and there are a lot of problem to check head and tail null values.

## Solution

#### Java (Map and DeLinkedList, passed on Leetcode. Lintcode cannot compile it)

``````public class LRUCache {

int key;
int value;
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}

}

}

node.pre.next = node.next;
node.next.pre = node.pre;
}

remove(node);
}

remove(last);
return last;
}

}

int capacity = 0;
int size  = 0;

public LRUCache(int capacity) {
this.capacity = capacity;
}

public int get(int key) {
if (node == null) {
return -1;
}

deList.moveToFirst(node);

return node.value;
}

public void put(int key, int value) {
if (node == null) {
if (size == capacity) {
map.remove(last.key);
--size;
}
map.put(key, node);
++size;
} else {
node.value = value;
deList.moveToFirst(node);
}
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
``````

#### Java (Map and arraylist. It is not O(1))

``````public class Solution {

private Map<Integer, Integer> values = new HashMap<Integer, Integer>();
private List<Integer> orderedKeys = new ArrayList<Integer>();
private int capacity = 0;
private int size = 0;

// @param capacity, an integer
public Solution(int capacity) {
this.capacity = capacity;
}

// @return an integer
public int get(int key) {
Integer value = values.get(key);
if (value == null) {
return -1;
}
orderedKeys.remove(Integer.valueOf(key));
return value;
}

// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
Integer val = values.get(key);
if (val == null) {
checkCapacity();
values.put(key, value);
++size;
} else {
values.put(key, value);
orderedKeys.remove(Integer.valueOf(key));