146. LRU Cache

class LRUCache {
    private LinkedHashMap<Integer, Integer> map;
    
    public LRUCache(int capacity) {
        this.map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        Integer value = map.get(key);
        return value == null ? -1 : value;
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

import java.util.HashMap;
import java.util.LinkedList;

class LRUCache {
    private HashMap<Integer, Integer> map;

    private LinkedList<Integer> queue;

    private int count;

    private final int capacity;

    public LRUCache(int capacity) {
        this.map = new HashMap<>(capacity);
        this.queue = new LinkedList<>();
        this.count = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            // move the most recently used element to the head of the queue
            queue.remove((Integer) key);
            queue.addFirst(key);

            // get value from map
            return map.get(key);
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // move the most recently used element to the head of the queue
            queue.remove((Integer) key);
            queue.addFirst(key);

            map.put(key, value);
        } else {
            // if the queue is empty, remove the eldest element
            if (count == capacity) {
                Integer removedKey = queue.removeLast();
                map.remove(removedKey);
            } else {
                count++;
            }
			
            // insert
            queue.addFirst(key);
            map.put(key, value);
        }
    }
}