Implement LRU Cache

class LRUCache {
    int cap;
    list<pair<int,int>> dll; // {key, val}, front = MRU
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        dll.splice(dll.begin(), dll, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            it->second->second = value;
            dll.splice(dll.begin(), dll, it->second);
            return;
        }
        if ((int)dll.size() == cap) {
            mp.erase(dll.back().first);
            dll.pop_back();
        }
        dll.push_front({key, value});
        mp[key] = dll.begin();
    }
};

import "container/list"

type LRUCache struct {
    cap int
    ll  *list.List
    mp  map[int]*list.Element
}

type entry struct {
    key, val int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{cap: capacity, ll: list.New(), mp: map[int]*list.Element{}}
}

func (c *LRUCache) Get(key int) int {
    if e, ok := c.mp[key]; ok {
        c.ll.MoveToFront(e)
        return e.Value.(*entry).val
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if e, ok := c.mp[key]; ok {
        e.Value.(*entry).val = value
        c.ll.MoveToFront(e)
        return
    }
    if c.ll.Len() == c.cap {
        back := c.ll.Back()
        delete(c.mp, back.Value.(*entry).key)
        c.ll.Remove(back)
    }
    e := c.ll.PushFront(&entry{key, value})
    c.mp[key] = e
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
            self.cache[key] = value
            return
        if len(self.cache) == self.cap:
            self.cache.popitem(last=False)
        self.cache[key] = value

class LRUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.cache = new Map(); // insertion-ordered
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, val);
        return val;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size === this.cap) {
            const oldest = this.cache.keys().next().value;
            this.cache.delete(oldest);
        }
        this.cache.set(key, value);
    }
}

class LRUCache {
    private final int cap;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.cache = new LinkedHashMap<>();
    }

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

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.remove(key);
        } else if (cache.size() == cap) {
            Iterator<Integer> it = cache.keySet().iterator();
            it.next();
            it.remove();
        }
        cache.put(key, value);
    }
}

class LRUCache {
    private cap: number;
    private cache: Map<number, number>; // insertion-ordered

    constructor(capacity: number) {
        this.cap = capacity;
        this.cache = new Map<number, number>();
    }

    get(key: number): number {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key)!;
        this.cache.delete(key);
        this.cache.set(key, val);
        return val;
    }

    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size === this.cap) {
            const oldest = this.cache.keys().next().value as number;
            this.cache.delete(oldest);
        }
        this.cache.set(key, value);
    }
}