You might have come across this problem in an interview or coding challenge. I went through the pains of trying to implement this algorithm without understanding what it’s used for so I hope that this will help you in understanding LRU Cache’s purpose.
Let’s first quickly go over what is cache. Computers have cache memory that temporarily stores the most frequently used data. It’s a great way to get the data that is used most often because the retrieval process is super fast. Computers also have memory but it’s more expensive to retrieve data from there. However, cache memory is limited in size and there needs to be a way to manage what data needs to be removed from the cache in order to store new data. That’s where LRU cache comes in. It’s a cache replacement algorithm that removes the least recently used data in order to make room for new data.
Suppose you have a app that displays some .png images on page load. Say you’d want to store them in your cache so that the images load fast for your users. Now, your user interacts with your page and those actions trigger new images to be loaded on the screen. You still want to provide them with blazing fast image load times, however, you run out of space in your cache.
Out with the old, in with the new! This is where you can use a cache replacement algorithm to remove an old image in your cache for a new image. LRU stands for least recently used and the idea is to remove the least recently used data to free up space for the new data.
While LRU Cache can somewhat be natural to reason about, the implementation is tricky. It exercises many of your programming fundamental skills and knowledge like using object oriented programming, knowledge of data structures, deciding on which data structure to use and why, functional patterns, understanding what state you need and how you’d keep track of your least recently used item.
As wise men have told me, reason your logic, write down the things that you need to do, and take it one step at a time. Do all of this before you code because there are a lot of parts in this algorithm. Good luck!
