LRU cache in O(1).

A cache has finite memory, so when it is full something has to go. LRU (least recently used) evicts the entry that has gone longest without being read or written (Week 0, Part 6, section 11.2): with capacity 4 and accesses A, B, C, D, A, B, inserting E evicts C. It is the policy behind most in-process caches and Memcached, and a classic "implement this" interview round.

Implement LRUCache(capacity):

Rules the tests check:

• get and put run in O(1): the hidden tests count key comparisons, and scanning a list on every access fails them.
• capacity below 1 raises ValueError.
• A miss doesn't change the order. Updating an existing key never evicts anything.
• Build the recency list yourself: collections.OrderedDict and functools.lru_cache are off limits, as they usually are in the interview.

In JavaScript and TypeScript the methods are get(key) (null on a miss), put(key, value), delete(key), a size getter in place of __len__, and order() (an array). A capacity below 1 throws a RangeError. A Map remembers insertion order, so "delete the key, set it again, evict map.keys().next().value" is JavaScript's OrderedDict, and it's off limits too: the rule test looks for .keys().next(), .values().next() and .entries().next(). Use the Map only to find a key's node. JavaScript can't count key comparisons, so the O(1) test counts the array elements that indexOf, splice, shift and the like walk over instead.