Build a class LRUCache that holds at most capacity key/value pairs and throws out the entry that has gone unused the longest when it runs out of room.
LRUCache(capacity)withcapacity >= 1.get(key)returns the stored value, or-1if the key is absent. Reading a key counts as using it.put(key, value)stores or overwrites the value and counts as using the key. If a new key makes the cache exceedcapacity, first remove the least recently used key.
Both methods must run in O(1) time. The tests do 200,000 operations on a cache with room for 50,000 keys, so tracking recency in a Python list (with remove/index/pop(0)) is too slow. Don't use OrderedDict or functools.lru_cache: the point is to build the structure yourself.
c = LRUCache(2)
c.put("x", 1)
c.put("y", 2)
c.get("x") # 1 ("y" is now the stalest)
c.put("z", 3) # evicts "y"
c.get("y") # -1
c.put("x", 9) # overwrite, no eviction
c.get("x") # 9
Show hint
A dict gives O(1) lookup but no order. Pair it with a structure that can move any entry to the "most recent" end, and drop the "least recent" end, in O(1); sentinel nodes at both ends remove the edge cases.