LRUCache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

• Time: O(n)
• Space: O(n)

public class LRUCache {
    private Map<Integer, Integer> map;
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        Integer val = map.get(key);
        if (val == null)
            return -1;
        map.remove(key);
        map.put(key, val);
        return val;
    }

    public void set(int key, int value) {
        map.remove(key);
        map.put(key, value);
        if (map.size() > capacity)
            map.remove(map.entrySet().iterator().next().getKey());
    }
}