Deviopath › Python

LRU Cache

Hard · Classes

An LRU (least recently used) cache holds at most capacity items. When it is full and a new key arrives, it throws away the key that was used longest ago. Both reading and writing a key count as "using" it.

collections.OrderedDict keeps keys in order and has move_to_end(key) and popitem(last=False) (removes the oldest). A plain dict also keeps insertion order, so popping a key and inserting it again moves it to the end.

Complete the LRUCache class:

- LRUCache(capacity): capacity is at least 1 - get(key): return the value, or -1 if the key is missing; a hit marks the key as most recently used - put(key, value): insert or update the key and mark it as most recently used; if this makes the cache too big, remove the least recently used key

Both methods should be O(1). The driver run_lru is already written.

Next: Trie Autocomplete