LRU cache
I had heard a lot about this interview question from people but honestly, I never studied it in school. Maybe I skipped one of those classes that talk about it 🙂
LRU stands for least recently used (add cache to that, it becomes LRU cache. But LRU could be of anything like LRU disk, LRU threads, etc.). When an interviewer asks you this design question (I consider it as a design question), they are not expecting you to explain how caching works and what cache is but are in fact looking for an algorithmic solution to the LRU problem.
So what do we mean by LRU? Suppose you have two cats of ages 1 and 2 and you are asked to let go of the one that’s older – you let go of the second cat. What did we do here? We compared the ages of the two cats and only kept the one that was younger. Something similar happens with LRU design questions. We want to keep X (could be cache, drives, threads, etc.) but when we run out of capacity, we have to let go of something and this something is decided based on what was not used in recent times.
Fig. 1. High-level LRU working
Source: http://katrinaeg.com/lru-cache.html
How do we maintain the least recently used items? One way is to maintain something like a hashmap of ages and based on what is oldest, we remove it. But what would be the time complexity of this solution? We will have to traverse the entire map to find the oldest age and thus, it would take O(n) time. See HERE for this solution.
Can we do better? Turns out we can if we maintain a doubly linked list (DLL). The oldest item would always remain at the back of the list while the youngest at the front. In this way, we can delete an item in O(1) time. Whenever we access an element from the list, we push it to the front since it then becomes the most recently used item.
A doubly linked list solution in C++ should ideally not use pointers if you are using STL. But if you still want to write your own doubly linked list, HERE is a solution. But if you want to use STL, take a look at THIS.
To surmise, LRU implementation is a popular interview question and not that hard to grasp the concept of it. Give yourself a few hours and see if you fully understand what LRU demands and ways of designing it.
Feel free to leave comments if you have any questions.