Design LRU Cache - Blog by Roman Glushko
While preparing for coding interviews, I went through a large number of algorithmic challenges. I found particularly interesting one subset of problems - challenges related to designing some tools that we all use and rarely stop and think about how they work.
Least Recently Used Cache is a key-value storage that has some capacity and a specific key eviction policy. Whenever it's specified in Gb, percentage of RAM or number of keys, the cache capacity is useful to prevent the storage from overflowing the available memory resources and shutting down unexpectedly.
This is where eviction is helpful. In the case of LRU policy, we can just remove key-values that were not accessed for the longest time a.k.a least-recently-used items. This is a pretty natural things to do and it's commonly used in such popular key-value storages as Redis.
Another part to pay attention to is cache. Cache is a kind of storage that is usually optimized for reading and retrieving information that would be time- or resource-consuming to calculate or collect without the cache.
