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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

Follow up:
Could you do both operations in O(1) time complexity?

Solution :
Forget about the O(1) solution, first you have to make it work properly!
There would be a list of Entry, the Entry has key, val, age. We can use position index to represent age, if use array of Entry to store data. When put or get, usually have to shift all elment. Not Efficient!
Try to use linked-list of Entry to store data, when put or get to update 'age' of entry, just need to change pointers. In this case, have to use head to record most recently used entry and tail to record least recently used entry, and use size and capacity to record if the list is full or not. And obviously double linked list is better since we have to record the current entry's pre entry to make it connect to current entry's post entry when remove current entry. In this way put and get would first try to find if key exist already or not, which is O(n) time complexity.
Think about doing space time trade-off, means using HashMap to record all the <key, Entry>. Thus, the entry retrival based on key would be O(1) time complexity.

Show me the code!

class LRUCache {
    class Entry{
        int key;
        int val;
        Entry post;
        Entry pre;
        public Entry(int key, int val){
            this.key = key;
            this.val = val;
            this.post = null;
            this.pre = null;
        }
    }
    
    Entry head;//record the newest item
    Entry tail;//record the oldest item
    Map<Integer, Entry> map = new HashMap<>();
        
    int capacity = 0;
    int size = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Entry entry = map.get(key);
        if(entry == null)
            return -1;
        adjustPst(entry);
        return entry.val;
    }
    
    public void put(int key, int value) {
        Entry entry = map.get(key);
        if(entry == null){
            if(size >= capacity){//remove tail if already full
                map.remove(tail.key);
                if(size == 1){
                    tail = null;
                    head = null;
                }else{
                    tail.pre.post = null;
                    tail = tail.pre;
                }
                size --;
            }
            entry = new Entry(key, value);
            if(head == null){
                head = entry;
                tail = entry;
            }else{
                entry.post = head;
                head.pre = entry;
                head = entry;
            }
            map.put(key, entry);
            size ++;
        }else{
            entry.val = value;
            adjustPst(entry);
        }
    }
    
    private void adjustPst(Entry entry){
        if(head != entry && tail != entry){
            entry.pre.post = entry.post;
            entry.post.pre = entry.pre;
            entry.pre = null;
            entry.post = head;
            head.pre = entry;
            head = entry;
        }else if(head != entry && tail == entry){
            tail = tail.pre;
            tail.post = null;
            entry.pre = null;
            entry.post = head;
            head.pre = entry;
            head = entry;
        }
        //do nothing if head == entry
    }
}

/**
 * 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);
 */