LRUCache.java

static class LRUCache {
	
	LinkedHashMap<Integer, Integer> map;
	// Linked List remain order of list
	int cap;
	
	public LRUCache(int capacity) {
		this.cap = capacity;
		map = new LinkedHashMap<>();
	}
	
	public int get(int key) {
		
		if (!map.containsKey(key)) {
			return -1;
		}
		
		int value = map.get(key);
		map.remove(key);
		map.put(key, value);
		return value;
	}
	
	public void put(int key, int value) {
		if (map.containsKey(key)) {
			map.remove(key);
			map.put(key, value);
		} else {
			map.put(key, value);
			if (map.size() > cap) {
				// Remove first element
				Integer firstKey = map.keySet().iterator().next();
				map.remove(firstKey);
			}
		}
	}
}