Build an LRUCache class. LRUCache(capacity) holds at most capacity keys. get(key) returns the key's value, or -1 if it is not there, and counts as using that key. put(key, value) adds or updates a key, which also counts as using it; if adding a key takes the cache over capacity, it first evicts the least recently used key. Both calls should take constant time on average, however many keys are stored.
Example
cache = LRUCache(2)cache.put(1, 1)cache.put(2, 2)cache.get(1) # 1cache.put(3, 3)cache.get(2) # -1cache.put(4, 4)cache.get(1) # -1cache.get(3) # 3cache.get(4) # 4
What this question tests
Tests the classic least-recently-used cache: a class whose every operation must stay fast however full it gets. It is one of the most frequently reported design-a-data-structure questions across big tech, and the follow-up is always "what is the complexity of each call?"
More Python interview questions