Implement an LRU cache

A browser can keep only a few parsed pages. When a new one arrives and the cache is full, drop the page nobody has touched for the longest time.

Implement LRUCache(capacity), a cache that evicts the least recently used entry once it would exceed its capacity.

• get(key) returns the stored value, or undefined when the key is absent.
• put(key, value) inserts or updates.
• size is the number of entries currently stored.

Both get and put count as using a key, so that key becomes the most recently used. Updating a key that is already present replaces its value and does not add an entry. When a put would exceed capacity, evict the least recently used entry.

Capacity 2:

const cache = new LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")    // 1, and "a" is now the most recent
cache.put("c", 3) // "b" is evicted
cache.get("b")    // undefined
cache.get("a")    // 1

Write a top-level LRUCache that works with new. A class or a constructor function both work. Do not use export or module.exports.

Optional: the same rules at capacity 1. The required tests use capacity 2.