33Implement an LRU cache

Implement an LRUCache class with a fixed capacity. When it is full and a new key is added, it evicts the least recently used key.

• get(key): return the value, or -1 if the key is not there. Reading a key makes it the most recently used.
• put(key, value): insert or update the key, making it the most recently used. If this pushes the size over capacity, evict the least recently used key.

const cache = new LRUCache(2);
cache.put(1, "one");
cache.put(2, "two");
cache.get(1); // "one" (1 is now the most recent)
cache.put(3, "three"); // evicts 2
cache.get(2); // -1

Requirements

• Both get and put run in O(1) on average.
• Updating an existing key never evicts anything.
• Expose size (the number of keys stored).